The answer is $1005$ and the idea is pigeonhole principle. For any $1005$ integers there are two which has either a sum or a difference divisible by $2009$. Say the integers are $a_1,\ldots,a_{1005}$. Then consider their absolute minimum remainder modulo $2009$. Without loss of generality, $|a_i|=i$, that the absolute value of the remainder of $a_i$ is $i$ for $i=1,...,1004$. If not, just consider a permutation of those integers. And if $i$ appears once, we don't want $\pm i$ to appear again. Thus, if we take even one integer after $1004$ integers, we get two numbers with a sum or difference divisible by $2009$. On the other hand consider $1,2,...,1004$. No two of them have a difference or sum divisible by $2009$.

The answer is $n=\boxed{1006}$. $n=1006$ is O.K. We consider the following $1005$ nests. $(0),(1,2008),(2,2007),\dots ,(1004,1005)\pmod{2009}$ We select $1006$ numbers,then we may select $2$ numbers from the same nest.Then the $2$ numbers satisfy the condition.$\blacksquare$ $n=1005$ is N.G. We select $0,1,2,\dots ,1004,$then there are no $2$ numbers which satisfy the condition.$\blacksquare$