Um programa que é merecidamente muito elogiado no Windows é o ITunes. É Freeware, ou seja, pode baixar quem quiser e usar . Costuma vir junto com um IPod, e agrupa as músicas de um modo bem organizado. Pode se buscar uma música, um álbum, um artista. Há também como gerar uma playlist aleatória. Realmente ajuda as pessoas que possuem algumas centenas de MP3 em seu computador. Mas tem um inconveniente: Não tem binários para Linux e é proprietário (i.e. não podemos abrir seu código fonte).

Mais que uma alternativa ao iTunes, o Amarok faz tudo isso e com uma vantagem é open source. Chamá-lo unicamente de player é um xingamento e tanto, dado que agrupa músicas, possibilita você a usar banco de dados para as músicas, faz a pesquisa automática das letras das músicas e ainda busca o artista na Wikipedia, tudo isso só clicando em abas!

Há também como se cadastrar no last.fm e a cada música que você tocar, aparecerá mais sugestões de coisas parecidas.

Acho que nunca vi um programa tão bom para gerenciar músicas e tão completo.

Porém, se você usa Ubuntu (ou não possui o KDE em sua máquina), só conseguirá utilizá-lo se instalar algumas bibliotecas do KDE, o que nem sempre vale a pena.