I think this is one of those problems where smart people think too hard. It has nothing to do with non engineers misunderstanding randomness or the human mind intrinsically superimposing structure. All it has to do with is being an algorithmic dj.
Users don't want a random playlist. They want their songs shuffled, and they want them shuffled in a way that keeps songs from the same album distributed far apart. No one presses the shuffle button to get satisfaction out of pure randomness. They press the button because they want to listen to music. If think your users are dumb because they don't understand randomness then you don't understand the job that shuffle is supposed to do.
Users don't want a random playlist. They want their songs shuffled, and they want them shuffled in a way that keeps songs from the same album distributed far apart. No one presses the shuffle button to get satisfaction out of pure randomness. They press the button because they want to listen to music. If think your users are dumb because they don't understand randomness then you don't understand the job that shuffle is supposed to do.