The smallest

An integer $n$ is expressible as the sum of two squares if and only if it is of the form $n = A B^2,$ where $A$ is divisible only by primes not congruent to $3 \bmod 4$ and $B$ is divisible only by primes congruent to $3 \bmod 4.$

Writing $A = 2^a p_1^{a_1} \cdots p_k^{a_k},$ the number of representations of $n$ as a sum of two squares is $r_2(n) = 4(a_1+1)(a_2+1)(\cdots)(a_k+1).$ This formula (and the previous paragraph) comes from facts about Gaussian integers .

If $n$ is not a square or twice a square, then the number of essentially different representations of $n$ as a sum of two squares is $r_2(n)/8$ (there are eight different ways to write $a^2+b^2$ as the sum of two squares if $a$ and $b$ are nonzero and distinct, by switching $a$ and $b$ and/or applying negative signs to one or both of them).

To make this number equal to $2,$ we need $(a_1+1)(a_2+1) = 4,$ so setting $a_1=a_2=1$ suggests taking $n = 5 \cdot 13,$ which can indeed be written as $65 = 1^2+8^2 = 4^2+7^2.$

It's clear that this is the smallest possibility for $n$ not equal to a square or twice a square, but there are only a few possibilities less than $65$ which are a square or twice a square, and those can be spot-checked using the above formula.

(Yes, this is not the fastest solution, but it generalizes pretty well.)