Ich benutze amarok. Der hat 'ne SQL-basierte Suche, kann Texte aus dem Internet holen und hat noch einige weitere nette Features.
Unter Windows nehme ich Winamp.