Regarding the fact that orienting the cube takes some time: if it's such a big problem for a competitor, maybe he should try to become color neutral, otherwise he'll have to rotate the cube.
Becoming BLD color-neutral is crazy, but this is just how it is, that's just how it works. We shouldn't change the rules because of that, cubes should be random.
The only option you thought about to rotate the cube randomly is throwing it up in the air? really? we could have a computer generate a random orientation, just like we do with scrambles, this is really not the problem.