I saw GJay a while ago and instantly fell in love with the concept... it has been said that there's way too much MP3 database managers in Freshmeat, but this has to be from the far, far corner of the better end.
GJay ("GTK+ DJ"), by Chuck Groom, is a *NIX program that assists in generating nice playlists for XMMS (or other programs that read the near-standard .m3u playlists). The program doesn't actually depend on XMMS, it's a separate program (which is only a good thing, most XMMS plugins that directly mess with playlists from within XMMS tend to make it a teensy bit unstable...) The program supports MP3, Ogg Vorbis and uncompressed .wav files.
Use of GJay couldn't be simpler. You add files to the list, and it starts analyzing the files on background. To make a playlist, go to Make Playlist tab, choose parameters (including length of the playlist), and hit "Make Playlist" - once generated, hit the play button and XMMS plays it.
What makes GJay so interesting is that it analyzes the frequencies of the songs, and also the BPM rate. These things can easily be taken into account when generating a smooth playlist... You can also assign the "color" and rating (0.0 to 5.0) of the song. Rating is interesting because you can pick songs that are above certain rating; the color is fairly arbitrary - for example, saturation (dark to bright) can represent mood and hue can represent the genre. You can use the hue and saturation values to affect generation.
You can find GJay from SourceForge.net (http://gjay.sourceforge.net/) and it's also available as a Debian package.