If you have a system with a fast sort/order by operation but a slow (or missing) shuffle, one trick that I sometimes use is to generate a new random number for each record, then sort by that random number.

Uniform sampling is also quite easy (and principled) - you can just take the first n records.