Throw $n$ balls into $n$ bins, and let $X_n$ be the max load. That is the number of balls in the fullest bin.  It is known that if the balls are thrown uniformly and independently at random then $\mathbb{E}(X_n)  = \Theta(\lg{n}/\lg{\lg{n}})$.  

If instead, for each ball considered sequentially we look at two bins chosen uniformly and independently at random, and throw the ball into the least full one (or a random one if they are equally full), then it is known that  $\mathbb{E}(X_n) = \Theta(\lg{\lg{n}})$, a dramatic decrease. See [this survey][1] for example for more discussion of this phenomenon. 


> If we still look at two bins for each ball and the bins are still selected uniformly but only with pairwise independence, what is a tight asymptotic upper bound for $\mathbb{E}(X_n)$?

We know that in the case of pairwise independence, if we just looked at one bin at a time, then a tight upper bound is $\mathbb{E}(X_n) = \Theta(\sqrt{n})$.  

  [1]: http://people.cs.umass.edu/~ramesh/Site/PUBLICATIONS_files/MRS01.pdf