IMMS is an intelligent playlist plug-in for XMMS that tracks your listening patterns and dynamically adapts to your taste. Has some clever frequency analysis, combined with skip counts. I’ll review it after I’ve used it for a while.
Best thing it’s as simple as “apt-get install imms”.
A nice thing about this application is this list of useful addons.