1. Don't repeat songs too soon. A record of the last 100 or so songs should be enough and doesn't use much memory. If shuffling a short playlist or album, don't repeat until they've all been played.
2. Don't attempt to group similar sounding songs together. I've never seen an algorithm succeed at this and it serves no aesthetic purpose. If I want to maintain a mood, I'll create a playlist, select songs manually, or just hit skip.
3. Don't ignore new material. If I add, rename, or reorganize music I don't want to do anything special for it to be included in the shuffle.
4. Don't roll your own random algorithm. Ever since shuffle play was introduced as a feature on CD players, there have been algorithms that will play the same N out of X songs in a collection, clearly using some kind of modulo-based function instead of a good quality PRNG. If your algorithm can permanently exclude songs, it's broken.
None of this helps with songs that should remain part of a suite or have a segue that is abruptly clipped, but some of those shouldn't be separate tracks to begin with.