I'm surprised nobody has mentioned it, but I use MixZing for playing all of my music and it is absolutely incredible. Its reccomendation engine is near perfect and it's free. Much better than the stock Droid music app.For those of you looking for podcasts look no further than google listen. it is great. built in search, resume, rss support and pretty good ui for use in the car dock. it also auto downloads over 3g or wifi (your choice) and adds the newly downloaded casts to your listen queue.
now, who knows of a good music player?
-rvictory