Solution:

The block $\{1000N, \ldots, 1000N + 999\}$ misses all squares exactly when some consecutive squares $x^2$ and $(x+1)^2$ jump over it, which requires $(x+1)^2 - x^2 = 2x + 1 \gt 1000,$ so $x \ge 500.$ In particular every block below $500^2 = 250000$ contains a square, so we search from there.

Write $x = 500 + a$ with $a \ge 0.$ Then $x^2 = 1000(250 + a) + a^2,$ so as long as $a^2 \lt 1000$ (that is, $a \le 31$), the square $x^2$ lies in block $250 + a;$ these cover blocks $250$ through $281.$ Block $251 + a$ is skipped exactly when $$(x+1)^2 = 1000(250 + a) + a^2 + 2a + 1001 \ge 1000(252 + a),$$ that is, $a^2 + 2a \ge 999.$ For $a \le 30$ this fails (so $(x+1)^2$ lands in block $251 + a$), and it first holds at $a = 31,$ since $961 + 62 = 1023.$

Indeed $531^2 = 281961$ and $532^2 = 283024$ straddle the block starting at $282000.$ The least such $N$ is $251 + 31 = 282.$