I'd like to second the Grooveshark recommendation, though I either don't have enough points to comment on the original reply (or just don't know how).
In any case, a key advantage to Grooveshark over Pandora is that you can play any song you want at any time, and can even replay it. Sometimes I get a song stuck in my head and I just want to hear it right now, Grooveshark let's me do that. On Pandora, I can type in the songs name and just hope I hear it sometime in the first 10-15 songs.
Grooveshark also has a mobile client for Android and iPhone, I'm an Android user myself and have found it works well on that platform.
Grooveshark doesn't have quite the same recommendation engine as Pandora/Last.fm. I find myself using it more as a personal on-line library of favorite songs or play lists I build myself and want to hear vs. a radio station interface that picks songs for me.