Foobar 2000 has a 'Shuffle Albums' mode. I guess other players would too.
Even if your music doesn't quite fit into that box, it could be abused to do what you want (multi song collections turn into albums given the same album name, a single file has some other album name so is it's own album).
I made sure to check that the mode respects order within the albums.
Edit: And you can tweak the album grouping, so you wouldn't have to destroy album tags to make it work, just use some custom tag for the grouping.
I should've mentioned earlier that I've run across that and found it not really suitable for my purposes; I have close to a hundred gigabytes of music, much of which is not properly tagged so that "Shuffle (albums)" does what I want. It's also not broken down into directories by piece (a lot of it's in FLAC/CUE-per-album format, and one album usually contains several pieces), so "Shuffle (directories)" wouldn't work either.
I appreciate you taking the time to mention it, though, all the same.
Edit in re: to your edit: True, but even so, I can't see a way of making that work that doesn't involve many hours of manual tagging effort, which is something I'm sort of trying to avoid.
Yeah, bad tags are a problem and they aren't any fun to fix.
I would think that you could mechanically recognize many of the multi track pieces though (and then just dump some identifier in a grouping tag). So it's "just" a scripting problem, at least if you ignore finding decent and reliable libraries to do the tagging.
Sure, I could do that, and I don't mind driving command-line tools to do the tag modification so that's no real problem, but even with a 99.9% success rate, the size of my music library makes manually fixing up the ones that don't come out right a considerable task -- to say nothing of identifying them in the first place, another problem which doesn't really admit of easy programmatic solution.
In theory, I suppose I should just block out a weekend day or so, put on my headphones, and bite the bullet. But being able to add playlists, as playlists, to playlists, would neatly solve the problem without requiring me to spend a day engaged in such drudgery, and would offer other UI benefits besides. What I've got right now works well enough to be going on with for most of my purposes, and I suppose I just keep hoping someone will come along and satisfy my now rather forlorn hopes as to the rest.
Even if your music doesn't quite fit into that box, it could be abused to do what you want (multi song collections turn into albums given the same album name, a single file has some other album name so is it's own album).
I made sure to check that the mode respects order within the albums.
Edit: And you can tweak the album grouping, so you wouldn't have to destroy album tags to make it work, just use some custom tag for the grouping.