Firstly: it can be that the results of PCA and PLS are different, since they have a different objective function. Especially if the covariance between $X$ and $Y$ is near zero, the PLS solution is not stable.
Secondly: it seems from your plots that you need to multiply the PCA or PLS component with -1. This is allowed, because the sign isn't identifiable ...
You're correct that an auto-encoder outputs the same dimension as the input, but it goes through a smaller hidden layer. Imagine a series of layers, from input to output, each with the following number of neurons:
1000 : 500 : 100 : 500 : 1000
The 1000-dimensional input is squeezed through a 100-dimensional middle layer. Once trained, if you remove the ...
*This would be better suited as a comment but I can not do that yet.
What I like to use as a rule of thumb, without really knowing anything domain specific about the data, is to have atleast as many examples as features. Of course this is not very helpful most of the time, but atleast the model has the potential to use every feature.
It's mostly guesswork as far as I can tell, but here's a good place to start: estimate the total information content of your dataset (not the sample size!) and compare it to the information content of your model parameters. Your model parameters had better contain much less information if you want to avoid overfitting.