[timonoko]

MP3-module from Aliexpress and some ESP-board with tiny display and micropython. Ten Euro.

You can make random search N in the MP3-module, because OFF/ON restarts and then you short NEXT-button wires N times.

[snapetom]

You forgot to add /s. In no universe would this suggestion be at all practical, and meets practically none of the criteria I'm looking for.

[timonoko]

Everything else is doable, expect maybe "lossless". But then, alas, WAV is as lossless as can be and memory is cheap.