Any question answered...

If I remember correctly, people complained that the ipod's shuffle wasn't random enough because it played back to back songs by the same artist or repeated songs etc. Apple responded by changing the software so this was less likely, which effectively made it less random than it was to start with.

Exactly this, Apple did do that. In fact I think you can change the probability of it playing subsequent songs by the same artist or from the same album in the settings. The common human perception of something that is random is actually more like an even distribution of elements. E.g., if you ask someone to draw dots on a page in a random way, they end up drawing them more or less evenly spaced, as opposed to a truly random distribution in which you'd expect to see clusters of dots.

It's like lottery numbers - the chance of the numbers being drawn as 1, 2, 3, 4, 5, 6 is exactly the same as them being drawn 22, 3, 14, 40, 7, 31, but people would have a hard time perceiving the former as a random outcome.