Yeah, I've noticed this too and think I understand what you're saying. It's like - in terms of data sampling (as in survey information) - it's not sampling evenly across the overall data. It's grabbing tracks from too tight an area in the playlist.
Lemme try to put it visually because I dont know that my words are getting there. Say the white space is a playlist and the black lines are the first however-many songs that are played:
It's like this [what it seems like it's doing]:
Vs. this [what it should be doing]:
Anyway, like you, at times I can have some pretty gigantic playlists goin on and the uneven randomness of the random play is something that keeps me from using the feature. I wish there was something to do about that.