  Let $q$ be an odd prime power. Let $f\in \mathbb{F}_q[x]$ be a polynomial
having degree at least $2$, $a\in \mathbb{F}_q$, and denote by $f^n$ the $n$-th
iteration of $f$. Let $\chi$ be the quadratic character of $\mathbb{F}_q$, and
$\mathcal{O}_f(a)$ the forward orbit of $a$ under iteration by $f$. Suppose
that the sequence $(\chi(f^n(a)))_{n\geq 1}$ is periodic, and $m$ is its
period. Assuming a mild and generic condition on $f$, we show that, up to a
constant, $m$ can be bounded from below by
$|\mathcal{O}_f(a)|/q^\frac{2\log_{2}(d)+1}{2\log_2(d)+2}$. More informally, we
prove that the period of the appearance of squares in an orbit of an element
provides an upper bound for the size of the orbit itself. Using a similar
method, we can also prove that, up to a constant, we cannot have more than
$q^\frac{2\log_2(d)+1}{2\log_2(d)+2}$ consecutive squares or non-squares in the
forward orbit of $a$. In addition, we provide a classification of all
polynomials for which our generic condition does not hold.
