To solve the problem of finding the smallest integer $n$ such that each subset of $\{1, 2, \ldots, 2004\}$ with $n$ elements has two distinct elements $a$ and $b$ for which $a^2 - b^2$ is a multiple of $2004$, we start by analyzing the structure of the number $2004$.

Firstly, factorize $2004$ into its prime components:

$$2004 = 2^2 \times 3 \times 167.$$

We want to ensure that for every subset of $\{1, 2, \ldots, 2004\}$ with $n$ elements, there are two elements $a$ and $b$ such that $a^2 - b^2 = (a-b)(a+b)$ is divisible by $2004$.

To achieve divisibility by $2004$, both $(a-b)$ and $(a+b)$ must collectively account for the prime factors $2^2, 3,$ and $167$.

### Step-by-step Process:

1. Divisibility by 4:
- For divisibility by $4 = 2^2$, both $a$ and $b$ must either be odd or both even, since $a^2 - b^2$ simplifies to $(a-b)(a+b)$, and a difference or sum of similar parity numbers will ensure divisibility by $4$.

2. Divisibility by 3:
- If $a \equiv b \pmod{3}$, then $a^2 \equiv b^2 \pmod{3}$, meaning $a^2 - b^2 \equiv 0 \pmod{3}$.

3. Divisibility by 167:
- A similar argument holds for $167$, as $a \equiv b \pmod{167}$ ensures $a^2 \equiv b^2 \pmod{167}$.

### Finding Smallest $n$:

To ensure divisibility by each prime factor, $a$ and $b$ must be congruent modulo $4$, $3$, and $167$. The smallest $n$ is determined by finding the largest possible size of a set of integers such that no two numbers satisfy these congruences.

Using the Chinese Remainder Theorem, the number of distinct groups of residues for modulo $12$ (lcm of $4$ and $3$) and modulo $167$ can efficiently compute the total size:

$$\text{Number of groups modulo } 12 = \frac{2004}{12} = 167,$$
$$\text{Number of groups modulo } 167 = \frac{2004}{167} = 12.$$

By the Chinese Remainder Theorem, the number of different congruence classes modulo $2004$ can be calculated as:

$$\frac{2004}{4} \times \frac{2004}{3} \times \frac{2004}{167} = 3 \times 4 \times 1 = 12.$$

To ensure that at least one pair $(a, b)$ exists with congruence, the subset must have an integer greater than 12 elements. Hence:

$$n = \left( \frac{2004}{12} + 1 \right) = 1003.$$

Thus, the smallest size $n$ of a subset where the condition holds is:
$$\boxed{1003}.$$