I couldn't find this on the wishlist, and I don't know good an idea this is.
I notice that for some reason, the random function picks out some songs quite a lot more than others - some songs have been played 3 times more than others despite them being on my computer for the same length of time and me not manually selecting any of them. Also, I like listening to songs I've just got hold of.
How about having an option to use proportional randomization - the lower a song's play count is, the higher its chance of being chosen.
If I had the know-how, I'd try writing a plugin for it, but alas, I don't