It's not clear whether there are $n$ or $n + 1$ points per row, but asymptotically this is irrelevant; I'll assume there are $n$ points per row. Choose a set of $S = cn^{\frac{5}{3}}$ points from the grid uniformly and at random, where $c$ is a positive constant to be determined later. The probability that a randomly chosen set of four points form the vertices of a square with sides parallel to the grid is \[\frac{\frac{(n - 1)n(2n - 1)}{6}}{\frac{(n^2)(n^2 - 1)(n^2 - 2)(n^2 - 3)}{24}} \le Cn^{-5}\] for some positive constant $C$ Then among $cn^{\frac{5}{3}}$ points, the expected number of squares with sides parallel to the grid is \[Cn^{-5}\binom{cn^{\frac{5}{3}}}{4} \le \frac{c^4Cn^{\frac{5}{3}}}{24} \] In particular, there exists a configuration in which there are at most this many squares. Removing all vertices of every such square, we are left with \[cn^{\frac{5}{3}} - \frac{c^4Cn^{\frac{5}{3}}}{6} = (c - \frac{c^4C}{6})n^{\frac{5}{3}}\] points. For some positive $c$ sufficiently small, the constant multiplier is positive, and we are done. My guess is $n^2$ is the best lower bound.