самый продвинутый проигрыватель - это mpg123 в виде:
playlist - список файлов, который можно создать даже через ls:
$ls -R /dirname > ./playlist
Поиск и сортировку можно делать опять же в консольке командами типа sort. Т.к. вообще нет графики, то и меньше проблем. Лично слушал музыку вообще без установленных иксов. Файл думается можно любого размера делать, все равно он запускает mpg123 на каждую новую строчку списка заново.