It would be awesome to have a random playback order and a history of played tracks to be able to skip upcoming tracks that are within a certain number of the tracks in the history.

Example: Random + Skip within last 20 tracks

This is preferable to Shuffle in my opinion because you can't end up in the same order if you forget the last played track.