Psychological Randomness
If you ask a person to give you a 'random' number from 1 to 20, you are more likely to hear some numbers than others. There have been experiments that numbers like 13 or 17 sound more random than numbers like 10 or 20. For example:
Results revealed that for the entire sample the greatest percentage of tickets chosen for the first four selections were "random" tickets. Further, the most commonly cited reason for selecting and changing a lottery ticket was perceived randomness. -- Underlying cognitions in the selection of lottery tickets
Despite having an equal chance of being picked from a hat, certain combinations of numbers are perceived as more random than others.
Note: Also see The Secret Lives of Numbers for something related, and awesome. It's a java applet showing how popular numbers are in search results. Phone numbers, tax forms, zip codes, famous dates, etc. show up more often than other more 'random' numbers and create some interesting patterns.
So, sometimes psychological randomness is more important than true randomness when dealing with perception.
One of the things I dislike about the program I use to play music (Foobar 2000) is that that the "Random song" feature will pick the same song twice in a row. For a random number generator, that is a fine result, all numbers should have an equal chance of being picked. However, for the purpose of a music player, this is not a psychologically random result. Most people use a "Random" or "Shuffle" feature to listen to a new, random arrangement of their songs (like a radio station). How often do you want to hear the same song twice in a row? If you want to hear the same song twice, why would you even use the "Random" feature in the first place?
I think "psychological randomness" should be one of the primary goals for any shuffle / random feature.
The easiest thing to do would be to keep a list of recently played tracks (at least ten), and when picking the next song, re-pick if the song is on that list. Another thing you could do is keep a shuffled version of the original list (a random permutation), then pick songs in order from that list.
But, once you start going down this path, it could be hard to stop :) Would it be 'random' for two songs from the same artist to play? Same album? The more data you look at about the song (artist, album, title, user rating, genre, lyrics, mood), the smarter your randomization could be. You could build your own recommendation system based on that song metadata. Pandora does a good job of that as an example. They even call themselves "a new kind of radio station."