Music Player Daemon (MPD) allows remote access for playing music (MP3, Ogg Vorbis, FLAC, AAC, Mod, and wave files) and managing playlists. MPD is designed for integrating a computer into a stereo system that provides control for music playback over a local network. It is also makes a great desktop music player, especially if you are a console junkie, like frontend options, or restart X often.I'm impressed. It's taking way less processor than Rhythmbox does, allows me to disconnect and reconnect clients (console and GTK), and I haven't been able to make it skip.
It even loaded all 1838 directories of my music archive without flinching, and lets me browse by filename as well as searching by id3 tag.
(PS: On Debian, apt-get install mpd mpc gmpc, then copy and edit the sample conffile in /usr/share/doc to /etc, and finally mkdir -p ~/.mpd/playlists; the last bit looks like a bug workaround.)