Am just here to nitpick, but the 5 disk CD changer behavior that you just described is not true randomness (by definition).
Shuffle (mostly) used to do what you expected when you had a medium like CD with a small number of tracks.
As the number of available tracks grew, the definition became less and less obvious.
With a service like Spotify, you could design an entire multi-page specification to cover all the different possible "shuffle" options you could give users - all of which would be useful in at least some settings.
Instead of which users get one button and some guessing.