Você já considerou o media player VLC ?
- é gratuito e de código aberto.
- Se você abrir uma pasta, todos os arquivos dessa pasta (e subpastas) serão reproduzidos.
- Tem um botão de ordem aleatória (na captura de tela, aquela que se parece com uma forma de onda na parte inferior do player).
- Não sei ao certo o tamanho de uma pegada que você precisa, mas geralmente vejo isso usando entre 30 e 50 MB de memória.
- Ele pode definitivamente tocar os codecs que você mencionou, e praticamente qualquer outra coisa que você queira lançar nele.