Solution:
We show that the least integer with the desired property is $1006$. We write $2009 = 2 \cdot 1004 + 1$.

Consider the set $\{1005, 1006, \ldots, 2009\}$, which contains $1005$ integers. The sum of every pair of distinct numbers from this set lies between $2011$ and $4017$, none of which is divisible by $2009$. On the other hand, the (absolute) difference between two distinct integers from this set lies between $1$ and $1004$, none of which again is divisible by $2009$. It follows that the smallest integer with the desired property is at least $1006$.

Let $A$ be a set of $1006$ integers. If there are two numbers in $A$ that have the same remainder when divided by $2009$, then we are done.

Suppose, on the contrary, that all the $1006$ remainders of the integers in $A$ modulo $2009$ are all different. Thus, the set of remainders is a $1006$-element subset of the set $\{0, 1, \ldots, 2008\}$. One can also consider the remainders as forming a $1006$-element subset of the set $X = \{-1004, -1003, \ldots, -1, 0, 1, 2, \ldots, 1004\}$. Every $1006$-element subset of $X$ contains two elements whose sum is zero. Thus, $A$ contains two numbers whose sum is divisible by $2009$. Since $|A| = 1006$, we deduce that $1006$ is the least integer with the desired property.