There's a bit of confusion around this, but "deep learning" is nearly interchangeable with "neural networks". So PCA, for instance, isn't deep learning (which definitely doesn't make it bad, it's just definitionally not deep learning ie not a neural network).
Now, as far as the difference between PCA and eg an autoencoder (which is similar to an RBM, but different--both RBMs and autoencoders are "deep neural networks")--well, PCA just learns a linear mapping. You can stack PCAs on top of each other I guess, but it is functionally equivalent to a single layer. So it makes certain assumptions about the behavior of the data--specifically, that it's linear.
A neural network layer calculation looks like this: nonlin(Wx + b) A deep neural network forward pass looks something like this:
W3 .* nonlin(W2 .* nonlin(W1 .* INPUT+b1)+ b2) + b3)
Nonlin can mean a variety of things. Usually tanh, sigmoid, or max(0,x). If you remove those nonlinearities, it basically becomes like PCA, like a model that learns a linear mapping. When you have those nonlinearities, you get a non-linear mapping which, theoretically, lets you address a wider variety of problems.
But yeah, if you want to learn about deep learning, just learn about neural networks. It's the same thing.
Also, re: your point on local minima--on the upper end of experiments that have been done, you've got over a billion parameters. 10 million parameters would be on the relatively small side. I think it's reasonable for there to be a variety of possible solutions to any given problem, and the whole idea is that we're using models that are very flexible due to their high capacity. The problem historically has been using the capacity effectively. However, regularization methods like dropout help a lot, and I've found it's easier to think of neural networks as "feature learners". Each one of those neurons is theoretically a feature its learning. And even still, if you look at the features that are learned by convolutional nets (which are easier to visualize due to their being used on vision problems), they tend to arrive at similar features even though it starts from fairly different initializations.