I've spent a lot of time searching for just the perfect music players, and I've gone through a lot... just to name a few:
Stock Android 2.x (there is a forked version on the Play Store called Android Music by JRT Studio), which I've used for a good long while, with no major complaints other than the lack of lock screen controls, lack lack of persistent notification icon (causes notification bar to auto-close when skipping songs).
WinAmp - my favorite until they came out with a Pro version and added nagging in the free version
Google Play Music - had some minor performance issues; don't like how music is organized (streaming optimized)
Rocket Player - also made by JRT Studio - too flashy, performance issues
PowerAmp
DoubleTwist - haven't used in a while, but I don't recall liking it
Meridian
Probably a few others
And now, without further adu, my favorite music players:
Apollo (CM10 stock music) - baked into most CyanogenMod ROMs. Forked version on Play store called Nexmusic. There is also Omich, which is a fork of Apollo and Google Play Music - This play is quick, lightweight, and great with fetching album art. My biggest gripe is that I can't go to a previous song in shuffle if I accidentally skip one I actually want to listen to. Not sure if issue(s) are present in the forks, since I happen to be using a CM based ROM. NOTE there is a crummy music of the same name on the Google Play store, which does not resemble the on baked into CyanogenMod in any way. I'd stay away from that, even if it is open-source.
Vanilla Music - forked from an the abandoned Vanilla Music Player, this is "the" perfect music player. Has every feature you could possible want - playlists, que management, shuffle, lock screen controls, gesture controls (swipe to skip), lots of options to customize, all in a minimal, lightweight, open-source package.