Earlier quoted context omitted.
From what I remember, Pandora did that really well. It's been a while since I've used it, but their classification system was really cool.
Yes, this is still true, and it's great. Within the songs and artists that typically play on my Pandora stations, it will play similar songs in clusters, with the exception that it won't play the exact same artist twice in close succession. This makes the playlist a lot better (in my opinion). The only quirk I've noticed is when the same person has multiple bands... I've had it play Jack White or Les Claypool 4 times…
I'd much rather have these sub-genres woven together with changing styles at each track boundary, as a sort of counterpoint.
If I can remember all the way back to when I used to make my own "mix tapes" transferred from vinyl records, I think I used to do this sort of interleaving. So, I think my preference existed before I ever experienced the shuffle of a 5 or 10 disc Sony CD changers, which usually changed discs on every track change and avoided any repeats until the entire set was done.
Because of my preference for shuffle, I used to burn a CD or two for use in rental cars, where I added a pseudo-random prefix to the file names. This gave me a shuffled play when the in-dash player was set to just play sequentially, so I didn't have to discover a random mode with repeats in one particular car...