Let $a_1 = 21$ and inductively add new elements by the following procedure, suppose we have until $a_k$. We're going to always have $a_i$ to have two new $3 \pmod 4$ primes dividing it. So let the primes so far be $p_1, p_2, \cdots, p_{2k}$. Construct two new primes $p,q$ such that both satisfy $\left(\frac{p_i}{p} \right) = 1$ as well as $3 \pmod 4$ for all $1 \le i \le 2k$ which is possible by Dirichlet. Note that by quadratic reciprocity, we have $\left(\frac{p}{p_i} \right) = -1$ too. I claim this works. Suppose that for some prime $p_k$, we have $p_k | a^n + b^n \implies \left(\frac{a}{b} \right)^n \equiv -1 \pmod {p_k}$. But by the way we have constructed the numbers, both $a,b$ are QR's $\pmod {p_k}$ (since each has $2$ primes dividing them which are both QR's or NQR's). Therefore, $\frac{a}{b}$ is a QR as well, so we have $z^2 \equiv -1 \pmod {p_k}$. But $p_k \equiv 3 \pmod 4$ so this is impossible. So this indeed works. $\blacksquare$

The set $\{ p_1^2, p_2^2, \dots, p_n^2 \}$ where $p_i \equiv 3 \pmod{4}$ for all $1 \le i \le n$ works. To prove that this works, suppose that for some $i,j,k$, we have $p_i \mid (p_j^n)^2 + (p_k^n)^2$, we must then have $p_i \mid p_j^n$ and $p_i \mid p_k^n$, which is clearly impossible as $i,j,k$ are of different index.