One day this will happen, and classical music enthusiasts everywhere will rejoice.
I'd really like for someone to make a music player or online store that worked better with classical music. Hell, I'd settle for one that didn't suck.
That might not be trivial at this stage. But yeah, I agree, the trickiest part would be crafting an intuitive UI around the feature.
If you're shuffle playing and the next song in the queue has a non-empty group tag, remove it from the queue and instead add the whole group in the correct order. Everything else should be handled the same.
It might be a bad way of handling it (and if it is, I'd be glad to know why). But that's how I would implement such a feature.
Then you could show a broken chain link if a linked track is shown in a view by itself sans sibling(s).
That type of UI would be simple enough when you want to link tracks that appear in sequence on an album. Are there any use cases for the ability to link unrelated tracks X Y Z together? Probably not. Playlisting pretty much covers all that functionality.
I don't use this plugin myself but this looks like it's exactly what you want...
As for shuffling your entire library, I don't understand why you'd want to do that. I get in the mood for certain genres; I don't want to jump from Rainbow to nordloef to Massive Attack randomly over the course of 10 minutes.
Another nice feature it has, is that it lets you handle albums with various artists as one entity, that is, you can set those tracks as "part of a compilation".
However, you can right click a group of tracks, then edit the info to add a unique Grouping label. This allows you to shuffle by grouping.
In fact, iTunes purchases - at least some of them - already include this. Screenshot: http://cl.ly/image/3w0R0y1I0E0V