I've started exploring Last.fm now as an alternative and/or complement to Pandora which I still use.
I haven't yet fully understood how Last.fm works but I'm going to try to learn it the same way you learn to use a new wrist watch: baby steps.
The standalone player application works great on my mac at home but the Linux version segmentation faulted before the music even started so I'm going to use a much more interesting alternative on Linux which is to play Last.fm inside Amarok (which is tonnes better than iTunes by the way). Sadly the pause keyboard command doesn't seem to work.
One thing I do love about Pandora, is the ability to shuffle between various stations/channels. In Pandora I've got one station of heavy metal and one for Frank Zappa type music (amongst others) and if I stay for too long on one station it gets a bit boring. Let's hope this is possible with Last.fm too.
Last.fm just keeps a record of every track you listen to. It then compares your list to the lists of others and makes recommendations based on the degree of similarity.
Use Last.fm to generate dynamic playlists in Amarok - it's probably the best feature of any media player. Amarok's logo is "rediscover your music" and that feature goes a long way toward doing so.