One quick upper bound for the axis-parallel rectangle case for large $n$: Fix an arbitrary arrangement of $4n$ points.  Then there are at most $cn^4$ distinct subsets of $2n$ points that lie inside axis-parallel rectangles containing exactly $2n$ points (the points in a rectangle are determined by an uppermost, lowermost, leftmost, and rightmost point).  

For any fixed rectangle containing $2n$ points, the proportion of lotteries for which that rectangle beats $n+C\sqrt{n \log n}$ is $o(n^{-4})$ for sufficiently large $C$, by the same tail bounds you linked to.  By the union bound, it follows that with probability approaching $1$ none of the axis-parallel rectangles beat $n+C \sqrt{n \log n}$.