Android: The Music app that comes pre-loaded on Android phones can be described, generously, as functional. Cubed, a music player with better looks, great features and automatic album art grabbing, is what you should consider using instead.
The two main caveats to labelling Cubed as a total replacement are that it's in beta and under active development at the moment, and may become a paid app or change features in the near future. That said, even at this early, semi-hidden stage, Cubed (named with the superscript "3" in the Market) is a much better experience.
You get three views of your album collection — a cube that rotates up and down between albums, and left to right for alphabetical search, an album art wall and a "Boring" list view. Cubed automatically grabs new album art when you load new music to your phone, and can "theme" those album covers to match one or two different looks. The player controls themselves are functional, though, like Kevin Tofel, I found the in-track audio scrubbing a bit wonky, and playlist creation could be a little neater. If you're a Last.fm user, there's a scrobbling tool you can get at in the options, and there's a Concerts Cubed plug-in that shows when the artists on your microSD card and others are playing nearby.
Cubed is a free (and open-source) download from the Android market, though it's not easy to search out. Consider using the QR code with a Barcode Scanner app to grab it from the jkOnTheRun via link.