My primary use for my droid is as a music player. My findings thus far:
Pandora: This is by far my favorite music app; I flip around between artist-defined stations and custom stations constantly, and all of them are surprisingly spot-on. Many artists I now follow were discovered through Pandora. All-and-all, this app is great for discovering new music as well as listening to what you like, but be prepared to create many stations and flip between them. No ads, but limited skipping (6x/station).
Slacker: Pandora's kid sister. I like and use slacker for the genre-specific channels, but I find that any band-specific channels are often quite repetitive. I have a bunch of channels and switch between them constantly, but I'm not often surprised by anything new once I've listened for a bit. Ads (for slacker) and limited (6x/station) skipping.
Last.FM: I admit, I usually use Last.fm set to "my library." This plays back my library and closely related tracks, but streamed instead of locally. Tis okay, but not particularly awesome. I find the interface too unwieldy during normal playback to use as often as the others. (I have yet to encounter an ad or a skip limit. Very good at finding topical music.)
DroidLive: Shoutcast app, very different from the Pandora/Slacker model. Pretty much like listening to regular radio stations (ads, no skipping and externally mixed, but a good selection of stations.) Good for checking out what's popular, but it seems more geared towards the latest top 40 and specific genres than finding something new. I haven't dug in enough to say one way or the other, and finding a general station is often the best way to discover new music. (No skipping, ads...similar to broadcast radio.)
Verdict? I use all of them, and would be happy to find more.
No one says you need to use only one.