Gnome Music Player Client (GMPC) + MPD - Just WOW
GMPC, or Gnome Music Player Client is a lightweight client for MPD, extendable through plug-ins: alarm, album view, AWN applet, dynamic playlist, fullscreen info, jamendo, last.fm, libnotify, lirc, lyrdb, lyricsplugin, lyricwiki, magnatune, wikipedia info, taglib (for editing tags) and so on (in the latest version).
Even though through plugins, GMPC becomes a fully featured music player and manager, it's still one of the fastest applications of this kind: currently it handles a play queue with more than a 1.000.000 songs without a problem. I have a collection of almost 40.000 songs and GMPC uses about 30 mb of RAM with all the plugins installed (the author says that for it's database of 32.000 songs, it used 11 MB of RAM but I guess that was either an older version, or he didn't test it using all the plugins).
This article will cover installing the latest version of MPD and GMPC in Ubuntu (as well as setting everything up).