I remember many years ago the iTunes player had to include an option for "humanizing" the randomness of their shuffle play (or whatever they called it).
Turns out that good randomness didn't seem random to people. They might hear three songs in a row from the same album and think "that's not right, it should be random!" Of course, humans often have a different idea of what "random" is.
What I expect from a music player is to play all my songs in random order, such that once a song has been played, it is not picked again until all songs have been played.
There is a difference between randomly picking an element from a list and reordering a list in a random order. This is not a matter of how random really are the random numbers.
One of the classic radio stations in Chicago does this a couple times a year -- they play their entire catalog A-Z. I agree that it does come out pretty nice.
Turns out that good randomness didn't seem random to people. They might hear three songs in a row from the same album and think "that's not right, it should be random!" Of course, humans often have a different idea of what "random" is.