I use and have written about both services. Each allows you to find new music that you are likely to enjoy. Last.fm does this through analysis of what you listen to and like (and what others listen to and like). Pandora encodes different aspects of music and determines what you might like based on those factors.
Pandora is easier to use because it takes absolutely no setup and streams music on the site itself. Last.fm uses tagging and has social network aspects, but you have to download the player to listen to music.
I find Last.fm to be better at playing music I’ve heard before and like, whereas Pandora tends to introduce me to entirely new bands.
Both are excellent. Tonight, in honor of Fred, I’ll be listening to Last.fm.