Thanks! I now have the language to describe the highly annoying fact that the ipod shuffle algorithm seems to be pseudorandom when I wish it was quasirandom!
1. generate a random permutation of the playlist
2. play all the way through it
3. goto 1
1. let S = set of songs to be played
2. let N = number of songs
3. repeat until bored:
3.1. let R = set of last [N / 2] songs we played
3.2. pick a song at random from S \ R; play it
You may want to tweak step 3.2 to give higher probabilities of picking songs that haven't been played for longer.