[captaincrisp]

That seems like the real problem with Spotify shuffle. The thing that feels un-random about it is that it plays the exact same songs over and over again despite the humongous size of the playlist. It's not that it plays the same artist, or that every once in a while you get a repeat song. Once you get one repeat they're all repeats.

I wish it would randomly pick the next song from the entire playlist whenever it changed songs.

Though as you say it might already be doing this now. I don't remember feeling like I'm rotating through the same 30 or so songs recently. But also I did start working around it, so I may just not be noticing.