Call the center square of isolated square by isolated center, and consider set $S$ of isolated centers in that $a\times b$ rectangle. Suppose a $a\times b$ rectangle contains $n^2-n$ isolated squares, and take one with minimum $a\times b$. Let's prove that the minimum of $a+b$ is $4n$. For a grid square $X$ located at $(x_0,y_0)$, partition the plane into five parts: $\{X\}$ and $A^+(X),B^+(X),A^-(X),B^-(X)$ which denotes $A^+(X)=\{(x,y)|x+y > x_{0}+y_{0}, x-y \geq x_0-y_0\}$ $B^+(X)=\{(x,y)|x+y \geq x_0+y_0,x-y < x_{0}-y_{0}\}$ $A^-(X)=\{(x,y)|x+y < x_{0}+y_{0},x-y \leq x_0-y_0\}$ $B^-(X)=\{(x,y)|x+y \leq x_0+y_0,x-y > x_{0}-y_{0}\}$ Briefly, they mean rightside, upside, leftside, downside, respectively. Note that $X\in A^+(Y)\Leftrightarrow Y\in A^-(X)$, and similarly $X\in A^+(Y)\Leftrightarrow Y\in A^-(X)$. Define an order $(S,\prec)$ such that $X\prec Y\Leftrightarrow Y\in A^+(X)$, which becomes an order indeed. Consider max length chain $U$ and max length antichain $V$. Say they have length $p,q$. Note that $|U\cap V|$ is at most 1, since $V$ doesn't have any 2 comparable elements. Let the chain be $U_{1},\cdots, U_{p}$ in increasing order of $x$ coordinate, and let the antichain be $V_{1},\cdots, V_{q}$ in increasing order of $y$ coordinate. For convenience, let $U_0,U_{p+1},V_0,V_{q+1}$ denote $(-\infty, 0), (\infty, 0), (0,-\infty), (0,\infty)$, respectively. Then $U_{i+1}\in A^+(U_i)$ for all $0\leq i \leq p$ and $V_{i+1}\in B^+(V_i)$ for all $0\leq i \leq q$. Define sets $Y^+=\bigcup_{i=0}^{p}A^+(U_i)\cap B^+(U_{i+1})$ and $Y^-=\bigcup_{i=0}^{p}A^+(U_i)\cap B^-(U_{i+1})$. Similarly define $X^+=\bigcup_{i=0}^{q}B^+(V_i)\cap A^+(V_{i+1})$ and $X^-=\bigcup_{i=0}^{q}B^+(V_i)\cap A^-(V_{i+1})$. Suppose an isolated center is not contained in $U, Y^+,Y^-$. Then by definition it has to be contained in $A^+(U_i)\cap A^-(U_{i+1})$ for some $0\leq i\leq p$, which contradicts to maximality of $U$. Therefore $Y^+,Y^-$ are a partition of $S\setminus U$: they represents upside and downside of $U$. Similarly, $X^+,X^-$ separates $S\setminus V$, which represents rightside and leftside of $V$. Step 1. Such $a\times b$ rectangle contains at least $4n^2-2$ unit grid squares. Our goal is place some disjoint lattice polygons inside the $a\times b$ rectangle, so that sum of their areas is $4n^2-2$ or over. Now, place tiles like: - If $U\cap V$ has an element, place a $3\times 3$ tile centered at it.

- On elements in $U\cap X^+$, place $3\times 2$ tiles

centered at it.

- On elements in $U\cap X^-$, place $3\times 2$ tiles

centered at it.

- On elements in $V\cap Y^+$, place $2\times 3$ tiles

centered at it.

- On elements in $V\cap Y^-$, place $2\times 3$ tiles

centered at it.

- On elements in $X^+\cap Y^+$, place $2\times 2$ tiles

centered at it.

- On elements in $X^-\cap Y^+$, place $2\times 2$ tiles

centered at it.

- On elements in $X^-\cap Y^-$, place $2\times 2$ tiles

centered at it.

- On elements in $X^+\cap Y^-$, place $2\times 2$ tiles

centered at it. Now I'll prove that they're disjoint indeed: Note that any 2 isolated centers don't share a vertex. Hence there are at most 1 isolated center in any $2\times 2$ square, which means $2\times 2$ tiles are disjoint with others. Also, note that from the structure of $A^+$, $U_{i}$ and $U_{i+1}$ has x-coordinate difference at least 2, which means any 2 $3\times 2$ tiles are disjoint. Next, note that for any $U_{i}$ and $U_{j}$, $B^+(U_i)$ and $B^-(U_j)$ is disjoint. Therefore, any $3\times 2$ tile and $2\times 3$ tile are disjoint. It follows that if $U\cap V$ is not empty, the $3\times 3$ tile is disjoint too. Now count the area: Note that $pq\geq |S|=n^2-n$ by Dilworth's theorem, which means $p+q\geq 2n-1$. Therefore, the area is at least \[4|S|+2(|U\cup V|-|U\cap V|)+5|U\cap V| \geq 4|S|+2|U|+2|V|= 4(n^2-n)+2p+2q\geq 4n^2-2\]As desired. Step 2. $a+b\geq 4n$ if the rectangle has side parallel to the grid. Note that we can assume the rectangle has lattice points on each side by minimality, since we can scale down the rectangle. Now $a,b$ are integers and $ab\geq 4n^2-2$. Suppose $a+b\leq4n-1$ in contrary. Then $ab\leq 2n(2n-1)<4n^2-2$, so contradicition. Therefore $a+b\geq 4n$ in this case. Step 3. $ab\geq 4n^2$ if the rectangle has sides not parallel to the grid. By minimality, we can assume that the rectangle touches the polygon in Step 1 on each side. Now use some trigonometries: Let the four points be $A,B,C,D$ on the four sides. Obviously $ABCD$ is convex. Let the rectangle be $PQRS$ with $A\in PQ, B\in QR$ and so on. Let $AC\cap BD=X$, and let $\angle CAQ=x, \angle AXD=\theta, AC=a,BD=b$. Then $a+b$ is $a\sin x+b\cos(\theta-x)$, since $-\pi/2\leq \theta-x\leq \pi/2$, obviously. I'll prove the minimum occurs on the boundary: Indeed, let $f(x)=a\sin x+b\cos(\theta-x)$, then $f''(x)=-a\sin x-b\cos (\theta-x)<0$, which means it's concave function wrt $x$, therefore the minimum occurs on the boundary. Therefore, we can assume a side meets at least 2 lattice points with the polygon. Now count area that we didn't count in Step 1: Remainders which are adjacent to the slope. On that side with at least 2 lattice points, choose 2 closest lattice point, such that the vector is $(m,k)$ with $\gcd(m,k)=1$. And let $s$ be grid points inside triangle $(0,0), (m,0),(0,k)$. Then, by Pick's theorem $\frac{mk}{2}=s+\frac{m+k-1}{2}$, and we can count at most $s$ in the previous step: Therefore the remaining part is at least $\frac{m+k-1}{2}$. If $m+k\geq 5$, then $ab\geq 4n^2-2+\frac{m+k-1}{2}\geq 4n^2$ as desired. Now suppose $m+k\leq 4$, so without loss of generality $(m,k)=(1,1),(2,1),(3,1)$ since $\gcd(2,2)\neq 1$. Case 1. $(m,k)=(1,1)$, so the slope is 1. Note that if a lattice point of the polygon is in a side, the rectangle contains some square which contains the point. Therefore, at the vertices of the rectangle we have additional 4 $\frac{1}{\sqrt{2}}\times \frac{1}{\sqrt{2}}$ triangles, so we have $4n^2-2+\frac{1}{2}+1=4n^2-\frac{1}{2}$ now. But note that the side with 2 points has length at least $\frac{2}{\sqrt{2}}+\sqrt{2}=2\sqrt{2}$, which means there are at least 2 lattice point on the opposite side too. So we have additional area $\frac{1}{2}$ at the opposite side, as desired. Case 2. $(m,k)=(2,1)$, so the slope is $\frac{1}{2}$. With same logic, we get at least 4 $\frac{2}{\sqrt{5}}\times \frac{1}{\sqrt{5}}$ tiles, so the additional area is $1+\frac{4}{5}$ now. If opposite side contains 2 touching point with the polygon, it becomes at least 2, as desired. So suppose that the opposite side contains exactly 1 touching point. Calculating the length, we get the length is $\frac{8}{\sqrt{5}}$ which means the one point is midpoint of the side. However, then the remaining part on the vertex adjacent to the point, becomes $\frac{4}{\sqrt{5}}\times \frac{2}{\sqrt{5}}$ and $\frac{3}{\sqrt{5}}\times \frac{3}{2\sqrt{5}}$ tiles instead. So the additional area becomes at least $\frac{53}{20}$ as desired. Case 3. $(m.k)=(3,1)$, so the slope is $\frac{1}{3}$. With same logic, we get at least 4 $\frac{3}{\sqrt{10}}\times\frac{1}{\sqrt{10}}$ tiles, so the additional area is at least $\frac{3}{2}+4\cdot\frac{3}{10}=\frac{27}{10}$, which is greater than 2, as desired. Therefore, we get at least 2 additional area in all the cases, so $ab\geq 4n^2-2+2=4n^2$, so by AM-GM $a+b\geq 2\sqrt{ab}=4n$. Finally we get $a+b\geq 4n$ in all cases. As an example, just color $(x,y)$ black iff $2|x$ and $2|y$, then we can select $(2n-1)\times (2n+1)$ rectangle containing $n^2-n$ isolated squares. Therefore, the minimum of $a+b$ is $4n$.

I think there's a much simpler way to do this. Lovely problem by the way! I claim the minimum value of $a+b$ is $4n$. Step 1: Construction Color the grid as follows: choose any square and color it black, then make jumps of size two to the left, right up and down and color those squares black too, up to infinity. Notice that every black square is the center of exactly one $3$x$3$ isolated square. Now, take a rectangle of size $(2n+1)(2n-1)$ with a black square being one down and one right to the up-right corner. It obviously gives $n(n-1)$ desired $3$x$3$'s $\implies a+b \leq 4n$ Step 2: Lower Bound Pay attention to the centers of isolated $3$x$3$ squares, call them special. Now consider any coloring and any $a$x$b$ grid. Notice that no two special squares can share a side or vertex. That easily implies that any $1$x$k$ or $2$x$k$ strip contains at most $\lceil \frac{k}{2} \rceil$. We now consider the inner $a-2$x$b-2$ square, where all the special centers are. Dividing the square in $2$x$a$ and $1$x$a$ strips we arrive at the first important inequality: $\lceil \frac{a}{2} \rceil \lceil \frac{b}{2} \rceil \geq n(n-1)$ This is the inequality between the maximum number of special squares and the number of special squares inside $(a-2)$x$(b-2)$. $(\frac{a-1}{2})(\frac{b-1}{2}) \geq \lceil \frac{a}{2} \rceil \lceil \frac{b}{2} \rceil \geq n(n-1) \implies$ $\implies (\frac{a+b-2}{4})^2 \geq n(n-1)$ By $AM-GM$ inequality. Set $t=a+b$ for simplicity. $\frac{t}{4}-\frac{1}{2} \geq \sqrt{n(n-1)} \implies$ $\implies t \geq 4\sqrt{n(n-1)}+2$ Now we it remains to show the right hand side is $>4n-1$. $4\sqrt{n(n-1)}+2 > 4n-1 \iff$ $\iff 16n^2-16n > 16n^2-24n+9 \iff 8n > 9$ Which is true for $n \geq 2$, so we have $a+b \geq 4n$, confirming it is indeed the minimum $\square$