I also recall Steve Jobs explaining in a keynote once that they had made the shuffle feature less random in response to user feedback about not wanting to hear the same song twice in a listening period.

Aha... just found what I was thinking of. Quote from article:

As humans, when we come across random clusters we naturally superimpose a pattern. We instinctively project an order on the chaos. It's part of our psychological make-up. For example, when the iPod first came out and people started to use the shuffle feature, which plays songs in a random order, many people complained that it didn't work. They said that too often songs from the same album, or the same artist, came up one after another. Yet that's what randomness does - it creates counter-intuitively dense clusters.

In response to complaints from users, Apple CEO Steve Jobs changed the programming behind the feature: 'We're making it (the shuffle) less random to make it feel more random.' In other words, each new song now has to be significantly different from what came before, so as to conform to our expectation of randomness. Which isn't really random at all.

Read more: http://www.dailymail.co.uk/home/moslive/article-1334712/Huma...