CMus
This is one of the best, feature-rich players for console. Built using ncurses and thus offering a text user interface, CMus has several view modes, organizes your music by artist/album, provides playlists and a library view, a filebrowser, it allows searching, Last.fm/Libre.fm scrobbling via this script, and it uses Vi-like keyboard shortcuts. A complete review can be found here and a guide to using it here.
Homepage
CMus is a powerful, feature-rich music player for the terminal which uses the Ncurses library: