Audacity and XMMS 2 both were a lot worse for some reason (like slower, weird bugs, needlessly unneeded server/client model, ...)
In XMMS 1, you can have 10000s of songs in the playlist (i.e. your whole harddisk), and jump to any of them immediately by just pressing the "j" key and typing part of its name, and it remains blazing fast.
Not sure how Winamp was these days. I remember it was good at version 2, then starting from version 5 ("2 + 3"), it became bloated.
I also use XMMS as my primary media player. It "just works" and I don't need a lot of fancy stuff in a music player. XMMS for music, and VLC for video, that's pretty much all I need.
I think you mean audacious [1] not audacity [2] although both are useful tools (If you're not familiar, audacious is a media player that supports XMMS plugins and Winamp2 skins). But WRT Audacious vs XMMS, I've also noticed that audacious doesn't seem to scale as well as XMMS with a lot of songs in your playlist.