I'm getting a new Android phone, which I have discovered can take a ... rather large microSDXC card. Large enough that it's feasible to dump all of my music collection on it, and use it for my traveling music player.

Most of my collection is classical or related - about 8000 files total. My feature wish list is play by genre tag, custom playlists, and random play of playlist / selection. Integration with a Windows music player, so that I can generate the playlists there and transfer them over, would be nice. I'm currently using Songbird for my Windows player, I'd consider moving to something else for a sufficiently compelling case.

So, what's your favorite Android player, and why?