The 3-choices are exactly the binomial coefficients $p = \binom{k}{3}$ with $k \ge 1$. Without loss of generality we can consider consecutive $p$ and $q$, so that $p = \binom{k}{3}$ and $q = \binom{k+1}{3}$ for $k \ge 1$. For $k = 1, 2, 3, 4$ the required statement is true, because
$$\binom{1}{3} = 0 \quad \binom{2}{3} = 0 \quad \binom{3}{3} = 1 \quad \binom{4}{3} = 4$$
are perfect squares. It therefore suffices to show for all $k \ge 5$ that between $\binom{k}{3}$ and $\binom{k+1}{3}$ there is at least one perfect square.

Solution 1. Let $n$ be the largest integer for which $n^2$ does not exceed $\binom{k}{3}$, i.e. $n^2 \le \binom{k}{3} < (n+1)^2$. We are going to prove that
$$(n+1)^2 - n^2 = 2n + 1 < \binom{k+1}{3} - \binom{k}{3} = \binom{k}{2}$$
which will then imply the claim.
This inequality is equivalent to $2n < \binom{k}{2} - 1$. Since both sides are positive this is equivalent to $4n^2 < \binom{k}{2}^2 - 2\binom{k}{2} + 1$. Because $n^2 \le \binom{k}{3}$ it will be sufficient to show
$$\begin{gathered} 4\binom{k}{3} < \binom{k}{2}^2 - 2\binom{k}{2} + 1 \quad \text{or} \\ \frac{2k(k-1)(k-2)}{3} < \frac{k^2(k-1)^2}{4} - k(k-1) + 1. \end{gathered}$$
When we multiply by 12 and rearrange, this becomes
$$k(k-1) \left( 3k(k-1) - 12 - 8(k-2) + \frac{12}{k(k-1)} \right) > 0.$$
Since $\frac{12}{k(k-1)} > 0$, it suffices to prove that
$$3k(k-1) - 12 - 8(k-2) = 3k^2 - 11k + 4 = k(3k - 11) + 4 \ge 0$$
for all $k \ge 5$. But this is obvious, since $3k > 11$ whenever $k \ge 4$.

Solution 2. (Owen Barron) For any function $h$ we let
$$\Delta h(m) := h(m+1) - h(m).$$
For $f(n) = n^2$ and $g(k) = \binom{k}{3}$ we then have
$$\begin{aligned} \Delta f(n) &= (n+1)^2 - n^2 = 2n + 1 & \Delta^2 f(n) &= \Delta f(n+1) - \Delta f(n) = 2 \\ \Delta g(k) &= \binom{k+1}{3} - \binom{k}{3} = \binom{k}{2} & \Delta^2 g(k) &= \binom{k+1}{2} - \binom{k}{2} = k. \end{aligned}$$

In particular, $\Delta^2 f(n) < \Delta^2 g(k)$ for all $n \ge 0$ and all $k \ge 3$ and $\Delta g(k)$ grows faster than $\Delta f(n)$. We will now prove by induction that for all $k \ge 1$ there exists an integer $m$ such that $g(k) \le f(m) < g(k+1)$. Above, before solution 1, we have seen that this holds true for $k = 1, 2, 3, 4$. Moreover, we even have
$$\binom{4}{3} \le 2^2 < 3^2 < \binom{5}{3} \quad \text{i.e.} \quad g(4) \le f(2) < f(3) < g(5).$$

The inductive steps in our proof will proceed from stepping stone to stepping stone. Suppose now that $k \ge 4$ is a stepping stone and let $n \ge m$ be the largest integer for which
$$g(k) \le f(n-1) < f(n) < g(k+1), \quad (5)$$
then $g(k+1) \le f(n+1)$.
From (5) we get $f(n) < g(k+1)$ and $\Delta f(n) < \Delta g(k+1)$ and now prove
$$f(n+r) < g(k+r+1) \quad \text{and} \quad \Delta f(n+r) < \Delta g(k+r+1) \quad \text{for all } r \ge 0.$$
The statement is true for $r=0$ and to carry out induction we suppose it holds true for a fixed value of $r \ge 0$. We then have
$$\begin{aligned} f(n+r+1) &= f(n+r) + \Delta f(n+r) \\ &< g(k+r+1) + \Delta g(k+r+1) \\ &= g(k+r+2) \end{aligned}$$
and also
$$\begin{aligned} \Delta f(n+r+1) &= \Delta f(n+r) + \Delta^2 f(n+r) \\ &= \Delta f(n+r) + 2 \\ &< \Delta g(k+r+1) + k+r+1 \\ &= \Delta g(k+r+1) + \Delta^2 g(k+r+1) \\ &= \Delta g(k+r+2) \end{aligned}$$
as required.

If for all $r \ge 0$ we also have
$$g(k + r) \le f(n + r)$$
the problem is solved. Otherwise, there exists an integer $s \ge 1$ such that
$$\begin{aligned} g(k+r) &\le f(n+r) < g(k+r+1) \quad \text{for } 1 \le r \le s \quad \text{and} \\ g(k+s) &\le f(n+s) < f(n+s+1) < g(k+s+1). \end{aligned}$$
This means that $k + s$ is a stepping stone greater than $k$ which completes the proof by induction that for all $k \ge 1$ there exists an integer $m$ such that $g(k) \le f(m) < g(k + 1)$.

Solution 3. We are going to show that $\sqrt{\binom{k+1}{3}} - \sqrt{\binom{k}{3}} \ge 1$ which implies that the interval $[\sqrt{\binom{k}{3}}, \sqrt{\binom{k+1}{3}})$ contains an integer $n$. As seen at the start, we only need to prove this for $k \ge 4$. Writing $k = m + 2$ we wish to show
$$\sqrt{\frac{(m+3)(m+2)(m+1)}{6}} - \sqrt{\frac{(m+2)(m+1)m}{6}} \ge 1 \quad \text{for } m \ge 1.$$
We rewrite this as
$$\sqrt{(m+2)(m+1)} (\sqrt{(m+3)} - \sqrt{m}) \ge \sqrt{6}$$
and note that $(\sqrt{m+3} + \sqrt{m})(\sqrt{m+3} - \sqrt{m}) = 3$. After multiplying both sides of the inequality by $\sqrt{m+3} + \sqrt{m}$ and squaring, we obtain
$$3(m+2)(m+1) \ge 2(\sqrt{m+3} + \sqrt{m})^2 = 2(2m+3+2\sqrt{m(m+3)}).$$
As both sides of the inequality were positive, squaring could be reversed and so this inequality is equivalent to the one we wish to prove. We rearrange to
$$3m^2 + 5m \ge 4\sqrt{m(m+3)}$$
and square again to obtain the equivalent inequality
$$9m^4 + 30m^3 + 25m^2 \ge 16m^2 + 48m.$$
This rewrites as
$$9m^3 + 30m^2 + 9m \ge 48, \quad \text{i.e.} \quad 9m(m+1)^2 + 12m^2 \ge 48$$
which is true since for $m \ge 1$ we have $9m(m+1)^2 \ge 36$ and $12m^2 \ge 12$.