I like spotify but it's not the best for music discovery. I feel like the problem is you get no ratings or feedback when looking through playlists, so you just see lines and lines of artists and songs you don't know.
You can do spotify radio, which is essentially the same thing as pandora. I like Plug because if you pick a good room, it can expose you to a type of music you'd like, without it being TOO pigeonholed, a problem that exists with pandora/spotify radio.
Pandora only still exists because it was the first in the game, and it's the only thing old people are familiar with.