Cara isso é algo muito pessoal e os critérios de escolha muitas vezes subjetivos. O negócio é saber oque você realmente quer em relação as funçoes e ir testando os programas.
Aqui eu não gosto de manter bibliotecas de mp3, então gosto mais de tocadores simples e diretos, fiquei extremamente satisfeito com o Audacious. Para video eu usava o VLC, que é ótimo, mas passei para o Mplayer, depois o Mplayer com o frontend Gnome-Mplayer e finalmente o Mplayer com o frontend SMplayer.