I use Winamp.
Small, fast, efficient program, tons of various plugins available, and it plays almost every single kind of audio and video format. If it doesn't, you just download a plugin for it.
It has various library organization options, shuffle features, and as long as your album art is in a picture format it'll display it if you want it to.