I'm sure a lot of the perception has to do with how individual songs are rotated. If you have, say, a 1000 song playlist in a given week, but you play 100 of them much more frequently than the rest, you'll obviously have repetition of certain songs while simultaneously giving the appearance of some depth.
Also, I don't know how "randomly" song sets are generated--but (warning: statistical geekery ahead) if you pick the songs at random "with replacement" (meaning that the song gets thrown back in the bucket to be picked after it's played), the chance of repetition increases quite quickly with each song played.
Let's say you have a 300 song playlist--heck, let's make it 500. After the first song is played, the chance of repetition on the second song is 1/500. After the first two songs are played, the chance of repetition of either of those two songs is 1/250. After 4 songs, 1/125. After 8 songs, 1/62. After 16 songs, 1/31. After 32 songs, 1/15. And so on. Put your iPod on shuffle and you'd be surprised how much repetition you get from a "random" selection of songs.
Now, playsets aren't that random. PDs make sure that the same song (or even the same artist) doesn't come up again too soon. But after that point, especially with heavily rotated songs, the chance of repetition is surprisingly high.
The chance of hearing "Free Bird" two days in a row is not that great. But the chance of hearing a song (any song, could be Free Bird, could be Stairway to Heaven, could be Hotel California, could be The Joker, etc.) you heard yesterday is quite a bit higher.