Solution:
The answer is $n=5$. The desired tiling is shown in Figure 1. It is formed by translation from the L-shaped region in bold borders. Since none of the five squares in this region border on squares of like side length, neither does any square in the infinite tiling.

To show that $n \leq 4$ does not work, it is necessary to plow through many arrangements of the tiles until reaching a contradiction. We present one method of structuring the argument. Some square in the tiling must have minimal size. Its four sides must be covered by squares larger than itself. If one side is covered by squares that protrude on both ends (pictorially, $\square$ or $\square$ ), then it becomes impossible to cover the opposite side; consequently any minimal square must be covered by four squares in the pinwheel arrangement $\Vdash$.

Assume first that the smallest square is the $1 \times 1$ and it is surrounded by a $2 \times 2$ and a $3 \times 3$ in the manner of A, B, C in Figure 2. Now the upper left corner of $\mathrm{D}$ must be filled by a $4 \times 4$ (a $1 \times 1$ would lack the necessary pinwheel layout) and likewise there is a $3 \times 3$ at $\mathrm{E}$. Now the corner $\mathrm{F}$ cannot be filled with a $4 \times 4$ square without wrecking the pinwheel at $\mathrm{A}$, so it must be a $1 \times 1$. The space above $\mathrm{F}$ is now calling for either a $3 \times 3$ or a $4 \times 4$, either of which disrupts the pinwheel at $\mathrm{A}$. Thus the arrangement $\mathrm{ABC}$ at Figure 2 is impossible.

So if a $2 \times 2$ borders on a $1 \times 1$, the resulting cavity must be filled by a $4 \times 4$ as in $\mathrm{ABC}$ of Figure 3. The $3 \times 3$ at $\mathrm{D}$ is clear. The left side of the A-pinwheel must have a $3 \times 3$ ($E$) since a $4 \times 4$ would leave untilable space below $B$. The remaining spot on the pinwheel is necessarily occupied by a $2 \times 2$ ($F$). Now $AFE$ of Figure 3 is the same configuration as $ABC$ of Figure 2. Hence this case is also impossible. So a $2 \times 2$ cannot touch a $1 \times 1$.

Thus any $1 \times 1$ must be covered alternately by $3 \times 3$'s and $4 \times 4$'s as at $ABC$ of Figure 4. The $2 \times 2$ at $D$ follows immediately, and since a $1 \times 1$ cannot touch a $2 \times 2$, we must use a $4 \times 4$ at $\mathrm{E}$ and a $2 \times 2$ at $\mathrm{F}$. Now the space around $\mathrm{F}$ must be covered by a $3 \times 3$ and a $4 \times 4$ which is impossible.

We have left for last the case where there are no $1 \times 1$'s. Since a tiling using only $3 \times 3$'s and $4 \times 4$'s is clearly impossible, the minimal square must be $2 \times 2$, covered alternately by $3 \times 3$'s and $4 \times 4$'s as at $\mathrm{D}$ and $\mathrm{CBE}$ of Figure 4 (ignore square $A$). We derive the $2 \times 2$ at $\mathrm{F}$ and the resulting contradiction in the same manner as the preceding case.