OP, my perspective is similar to yours. My MS "Random" is far less so than what I have in iTunes on my iMac and iPhone. Even with USB Phantom Playing, I tend to hear more of the same songs out of the 6K on my USB stick in my MS, than I do using iTunes with the same wide selection of tracks.
While I could no longer get into details, and I don't want to debate the point, having been a programmer back in the dark ages, I had to write my own random number generator a couple times for applications I was involved with. IIRC, I found various seeds would make the resulting "randomness" more or less so. I simply suspect Tesla is doing something more primative for some reason that ends up selecting particular points in the same sequence more frequently than other algorithms may.
What I do on my MS to sort of get around it, is I sometimes randomly play all the songs on my USB stick, and at others just one Genre or another. My adding that little bit of selection on my own, combined with what Media Player Random does, seems to then let me hear a wider selection.