I'm very pleased with the improved performance of Random Mix on 6.5.1--my display doesn't hang much at all between tracks where it used to hang for 5-10 seconds. It's considerably more usable.

I also think it's "more random". I hate saying things like that, but I'm hearing songs and stuff that I haven't heard in a while. Now as far as I know this is a function of MySQL's random function, and I don't think MySQL was upgraded, so it's probably all in my head, but it's still neat.