I have to vote in favor of the Slacker Radio app. I paid to upgrade my membership and now I have unlimited skips and no ads (which weren't that intrusive anyway.) I love the app, despite the issues it has when I switch from Wi-fi to 3G or EDGE. (It'll frequently just stop playing altogether.)
Cached stations are fantastic ways for someone to discover new music and not have to worry about using 3G/EDGE to download the music. With my 16GB SD card I can store up to 25 stations.
I have yet to find a decent media player app for my Nexus One. Hopefully something good will turn up from all you fine people. The stock app is ugly and browsing for music is tedious and frustrating.
Pandora, hands-down. I used to use Pandora all the time at a former job, and my current employer frowns heavily upon the continuous use of streaming media on the company network. I'm so glad to be able to use it at work again.
I really like museek. It has a smart shuffle feature that if you are playing a song and skip it then it goes to a different genera or continues to play music of the same genera. It also has a cool feature that lets you scroll through album covers to find what you're looking for. The album covers don't always work but every update it gets better.
The stock is nice, but has no features. I found Museek awhile ago and use it all the time now. Its some what like genius in itunes(bleh). Its not perfect but its not too bad, it has good support tho so this should improve in time. The main reason why i love it tho is it seperates my music into all kinds of different tags. That and it makes it easy to search your music. You kind of have to have a lot of music(I have about 8 to 9 gigs) for it really be useful but great none the less.
Other than that I use Pandora because its so simple and easy to use, just wish it had like a concert alert; that would be nice.
Droidlive for streaming. I am also surprised that no one has mentioned MortPlayer. It has a widget that is very nice that does cover art. The player itself lets you skin the background with any wallpaper you want.
I love Last.fm. I set it up on my home PC with their "Scrobbler", kicked on iTunes, started up my top rated 250 songs, walked away and viola, my fav songs all available to me via the Last.fm app on my Droid. Love it! LOVE.......IT! So easy.