Você pode usar sort -R para reordenar a lista de arquivos em ordem "aleatória". O comando pode ser o seguinte:
find ~/Music -type f | sort -R | xargs -I + play +
Aqui find ~/Music -type f resulta em uma lista de todos os arquivos na subárvore Music , de forma recursiva. A lista de nomes de caminhos resultante é então "classificada" em uma ordem aleatória por sort -R e passada como argumentos para sucessivas invocações de play com alguns / muitos nomes de caminho de cada vez. Observe o uso de + como "replace string" para chamar o indivíduo play para cada arquivo de música.
(Edit: de acordo com o comentário de Warren abaixo, eu removi agora as aspas simples inúteis mas inofensivas para o segundo + .)