I love Spotify, well worth $10 a month (you can get it free with ads, $5 a month for double the bitrate and unlimited listening or $10 a month to get it on your smartphone, I use it on my iPhone every time I'm in the car) the sound quality is really good for a streaming service (~320kbps Ogg Vorbis) and it's pretty much just like listening to a 320kbps MP3. I've sent out every invite they've given me (I think 14 so far) and everyone I invited says they love it too.
The catalog is pretty good, I'd say 9/10 for music I listen to but overall it's more like 8/10 since it's missing a few huge names like Led Zeppelin, Tool, Metallica (off the top of my head) so I would advise you to try the free version for a few weeks and see if it has all the music you want.
I can't stand Pandora, I want a lot more control over the music I listen to so Spotify works for me but if you want a radio-like experience, Pandora is pretty great.
Edited by Remonster - 9/19/11 at 10:14pm