Every single person can have multiple definitions on what random means in different situations (use-cases).
My hypothesis is that people use the random or shuffle options when they don't know exactly what do they want to listen to, they have a nice collection (or have access to a huge database), and want to be surprised on what follows.
So, a truly random progression is never what you truly want!
Instead you want a good DJ, that will suprise you and keep the mood going.
Imaging the opposite. A truly randomized playlist out of a list of 100000 songs. Who would want a truly randomized progression? Imagine listening to Beethovens 6th part II, then Sepultura, then Dua Lipa, then Juzni Vetar, and then only after 20000 other songs forced upon you with no context, you will get to the 6th part III.
So, don't ask for true random. Ask for an option that will give you a nice progression, keep the tempo, keep the mood, ask you if it is good (or measure it somehow). Yes, you want to hear the oldies/goldies, but not only those, otherwise it will get boring, yes you also want to be educated, to hear some good songs that you have not heard about in the past, ... just some of the possibilities.
Playlists are a hot topic in the field of recommender systems these days, and personalized playlists, playlists adapted to your mood and liking and your swings in mood from time to time, are the real future in modern players.
Last years ACM Recommenders systems conference had an competition in exactly that - the challenge of automatic playlist continuation. See this link for more details including the publications that presented some of the results of the challenge.
http://www.recsyschallenge.com/2018