Oh crap! My carelessness ignores $a \equiv -b \pmod{1002}$. Also, I didn't even check that $\frac{1002}{2}=501$ wasn't prime. The hidden argument is completely wrong.

Batominovski wrote: The answer is $n=1003$. The set $\{1,2,\ldots,1002\}$ provides an example to show that $n \geq 1003$ is required. $502^2 - 500^2 = 2004$.

Consider $m:=1002=2\cdot3\cdot167$. We have $x^2 - y^2 =0 $ in $\mathbb{Z}_m$ if and only if $x=y$, $x=335y$, $x=667y$, or $x=1001y$. Define an equivalent relation $\sim$ on $\mathbb{Z}_m$ via $x \sim y$ if and only if $x^2=y^2$. We see that there are three kinds of equivalence classes of $\mathbb{Z}_m$ determined by $\sim$: 1) $[501]$ and $[1002]$, each of which contains a unique element, 2) $[k]$ where $3 \mid k$ or $167 \mid k$, but $501 \nmid k$,each of which contains exactly two elements, and 3) $[k]$ where $3 \nmid k$ and $167 \nmid k$, each of which contains four elements. There are only two equivalence classes of the first type, while there are $\frac{1}{2}\left(\frac{m}{3}+\frac{m}{167}-\frac{2m}{501}\right)=168$ equivalence classes of the second type, and there are $\frac{1}{4}\left(m-\frac{m}{3}-\frac{m}{167}+\frac{m}{501}\right)=166$ classes of the last type. In total, there are $2+168+166=336$ equivalence classes. Therefore, if we have at least $337$ integers, two of them $a$ and $b$ must fall into a same class, so $2004 \mid \left(a^2-b^2\right)$ must then follow. Thus, $n=337$. PS: How do we generalize this problem to find the minimum $n$ such that, if $n$ elements are randomly picked out from $\{1,2,\ldots,N\}$, then $N \mid a^2-b^2$ for some two distinct chosen elements $a$ and $b$? For $N \in \{2p,4p\}$, where $p$ is an odd prime, we have $n=\frac{(p+1)}{2}+2$. For $N \in \{2pq,4pq\}$, where $p$ and $q$ are distinct odd primes, we can show that $n=\frac{(p+1)(q+1)}{2}+1$.