Display results in random order

I have some taxonomies with hundreds of posts (Custom post types) assigned. People stop looking after the first 20 or so, meaning the same posts get all of the attention (when using filters).

It would be great if there was a way to randomly deliver the results, to give all posts a chance of being seen.

Or even better, a new select dropdown providing the ability to order by other ways (name, date added, random etc).

Thanks