I'm looking for an example to show my students of an algorithm for which randomization of some kind leads to better performance on average. And I don't want that randomization to be of the Monte Carlo sort. Rather, I want an algorithm whose randomization amounts to making a random choice instead of a deterministic one. So I guess, if I understand the terminology, I'm looking for a Las Vegas algorithm instead of a Monte Carlo one.
For example, Quicksort is $O(n\log n)$ on average, as is randomized quicksort. So this is of the type I want, the Las Vegas type, but the randomized version only performs better in the worst case.
More generally, I want a relatively simple example of a Las Vegas algorithm that, in practice, benefits from randomization.