I find both Pandora and Last.fm to be great for finding new music.
On the Mac, the Last.fm player is invasive. Any time it opens, it resets the Audio Midi Setup to 2ch-16bit and 44.1Khz. (I like to up-sample iTunes to 48Khz to 96Khz).
Last.fm also wants you to install a piece of software called Audioscrobbler that continually tells them what you are listening to on other players. I don't like the idea of that.