Spotify's algorithm doesn't do "songs I haven't heard in a while", it does " here's 20 songs from your playlist, have fun with it for the next few weeks. So even if I "songs I haven't heard in a while", Spotify's garbage algorithm is not it. At this rate, I'd much prefer an actually random playlist.

I've been having to work around it by copying over the playlist I was shuffled, running it through shuf, and then putting it in to a separate playlist, and lastly, disable shuffle. It's garbage, but it's better than what Spotify produces.

Yes, and isn't generating a random order, then playing the songs in the album/playlist in that generated order the best way to do that? Ie, no repeats until every song has been played. That's how the MIX button on my car CD player works, that's how my MP3 player works, and that's how the Phonograph music player on my phone works. Why should Spotify be any different?