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$ possible axis-parallel rectangles containing exactly $2n$ of them (the points in a rectangle are determined by a 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}$.