This included regular stratified sampling[2] as well as using quasi-random low-discrepancy sequences[3] like the Sobol sequence[4], which would "space out" the random samples.
Probably not terribly relevant for load balancing, but I did find the quasi-random stuff fascinating. How to make something "random enough" without being "too random".
edit: Though now I got a shower thought moment, could stratified sampling be used as a variant of the "two choices", even if each load-balancer worked independently? That is, each load-balancer stratifies the resources, and keeps a separate index to the current bin. Then for each request pick a random/suitable resource from the current bin and increment the bin index, wrapping when needed. Hmm...
[1]: https://en.wikipedia.org/wiki/Path_tracing
[2]: https://en.wikipedia.org/wiki/Stratified_sampling