Apparently if $N$ has a factor within $\sqrt[4] N$ of $\sqrt N$ then Fermat factorisation works in one step.
Specifically this would mean that for $r = \lfloor \sqrt N \rfloor +1$ we have $$r^2 - N = s^2$$ for some integer $s$.
I've tried bounding $r^2 -N$ in-between $s^2\pm1$ for some $s$ but haven't got anywhere, and I certainly don't know how to make use of that factor close to $\sqrt N$.
Can someone prove this?
A small correction: The algorithm starts with $r = \bigl\lceil \sqrt{N}\,\bigr\rceil$.
Usually, that's the same as $\lfloor \sqrt{N}\rfloor + 1$, but when $N$ is a square it's a difference that matters. A square $N$ of course has a factor within $\sqrt[4]{N}$ of $\sqrt{N}$, but $(\lfloor \sqrt{N}\rfloor + 1)^2 - N = 2\sqrt{N} + 1$ then rarely is a square too, so that we need to start with $r = \bigl\lceil \sqrt{N}\,\bigr\rceil$ to be sure to find a factor in the first step.
And of course, $N$ needs to be odd or divisible by $4$, since Fermat's method cannot be applied to $N \equiv 2 \pmod{4}$.
Having this out of the way, we can assume that $N$ is not a square and $N \not\equiv 2 \pmod{4}$.
Let $N = pq$ with $p < \sqrt{N} < q$ such that $q - \sqrt{N} < \sqrt[4]{N}$ or $\sqrt{N} - p < \sqrt[4]{N}$. If $q < \sqrt{N} + \sqrt[4]{N}$, then $$p = \frac{N}{q} > \frac{N}{\sqrt{N} + \sqrt[4]{N}} = \frac{N - \sqrt{N}}{\sqrt{N} + \sqrt[4]{N}} + \frac{\sqrt{N}}{\sqrt{N} + \sqrt[4]{N}} > \sqrt{N} - \sqrt[4]{N}\,,$$ from which we obtain $q - p < 2\sqrt[4]{N}$ and hence $$\biggl(\frac{q+p}{2}\biggr)^2 = N + \biggl(\frac{q-p}{2}\biggr)^2 < N + \sqrt{N}\,.$$ If $p > \sqrt{N} - \sqrt[4]{N}$, then $q$ may be slightly larger than $\sqrt{N} + \sqrt[4]{N}$: $$q = \frac{N}{p} < \frac{N}{\sqrt{N} - \sqrt[4]{N}} = \sqrt{N} + \sqrt[4]{N} + 1 + \frac{1}{\sqrt[4]{N} - 1}\,.$$ For $N > 16$ we thus have $q < \sqrt{N} + \sqrt[4]{N} + 2$, whence $q - p < 2\sqrt[4]{N} + 2$ and $$\biggl(\frac{q+p}{2}\biggr)^2 = N + \biggl(\frac{q-p}{2}\biggr)^2 < N + \sqrt{N} + 2\sqrt[4]{N} + 1\,.$$ However, since $N < (\lfloor \sqrt{N}\rfloor + 1)^2$ we have $$(\lfloor \sqrt{N}\rfloor + 2)^2 = (\lfloor \sqrt{N}\rfloor + 1)^2 + 2(\lfloor \sqrt{N}\rfloor + 1) + 1 > N + 2\sqrt{N} + 1 > N + \sqrt{N} + 2\sqrt[4]{N} + 1$$ for $N > 16$, as then $2\sqrt[4]{N} < \sqrt{N}$.
This implies that for $N > 16$ not a square and not $\equiv 2 \pmod{4}$, if $N = pq$ with one of $p,q$ within $\sqrt[4]{N}$ of $\sqrt{N}$, then $$\frac{q+p}{2} = \lfloor \sqrt{N}\rfloor + 1\,,$$ which shows that Fermat's method succeeds at the first step.
The cases $N = 3,5,7,8,11,12,13,15$ are dealt with by inspection. The equations $$3 = 2^2 - 1^2, \quad 5 = 3^2 - 2^2, \quad 8 = 3^2 - 1^2, \quad 12 = 4^2 - 2^2, \quad 15 = 4^2 - 1^2$$ show that the method succeeds at the first step for $N \in \{3,5,8,12,15\}$, and the primes $7,11,13$ have no factor within $\sqrt[4]{N}$ of $\sqrt{N}$ (which is a close call for $N = 7$, as $\sqrt{7} - \sqrt[4]{7} - 1 \approx 0.01917475$).
Altogether, when Fermat's method is applicable (i.e. $N \not \equiv 2 \pmod{4}$) and $N$ has a factor within $\sqrt[4]{N}$ of $\sqrt{N}$, then the method succeeds at the first step, $\bigl\lceil \sqrt{N}\,\bigr\rceil^2 - N$ is then a perfect square.