Generating a pseudo random Rubik's cube in $O(n^{2+\epsilon})$ time
Well, the easy answer is that you don't traverse the graph of moves, you just generate a random group element directly.  A non-face-center cubie in an NxNxN cube will have an orbit of size 8, 12, 24 or 48, with 8 being possible only for corner cuties and 12 only being possible for edge-center cubies with N odd.  Divide the cubies into orbits, then generate a random permutation for each orbit with the restriction that the total permutation across all orbits must be even.  Then generate orientations for all edge and corner cubies, with a mod-2 parity restriction on each edge orbit and a mod-3 parity restriction on the corners.
I believe that covers all of the parity issues with the order-N Rubik's cube group, which means this method would generate random cubes uniformly distributed across the group.
This takes $O(N^2)$ time.