The question above is about lower bounds, but I allow myself to comment about upper bounds: $\pi(n)$, the period function of the Fibonacci sequence mod $n$, satisfies $\pi(n)\leq 6n$ and equality holds for $n=2^i5^j$, $i,j\geq 1$. This fact is well known. In the 90's it was considered here as a puzzle to the monthly readers. $\pi(n)$ was also discussed in an elementary fashion in the 60's in this monthly paper.
But really, I want to share a little observation which forms a generalization of the above mentioned fact: denoting, for an element $g\in \mathrm{GL}_2(\mathbb{Z})$, by $\rho_g(n)$ the order of the image of $g$ in $\mathrm{GL}_2(\mathbb{Z}/n)$, $\rho_g(n)\leq 6n$. This is a generalization because $\rho_g(n)=\pi(n)$ for $ g= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$. Note that $\rho_g(n)$ divides $2\rho_{g^2}(n)$, thus it is enough to prove that for $g\in \mathrm{SL}_2(\mathbb{Z})$, $\rho_g(n)\leq 3n$. Let me now fix $g\in \mathrm{SL}_2(\mathbb{Z})$, denote $\rho(n)=\rho_g(n)$ and prove that indeed $\rho(n)\leq 3n$.
First note that, for natural $p$ and $n$, if $p$ divides $n$ then $\rho(pn)$ divides $p\rho(n)$. This follows by expanding the right hand side of $ g^{p\rho(n)}=(g^{\rho(n)})^p=(1+nh)^p$ and note that it is 1 mod $pn$. By induction we conclude that for every $k>1$, $\rho(p^k)$ divides $p^{k-1}\rho(p)$.
Assume now $p$ is a prime and note that $\rho(p)$ divides either $p-1,p+1$ or $2p$. Indeed, if $\bar{g}\in \mathrm{SL}_2(\mathbb{F}_p)$ is diagonalizable over $\mathbb{F}_p$ then its eigenvalues are in $\mathbb{F}_p^\times$ and their orders divides $p-1$, else, if $\bar{g}$ is diagonalizable over $\mathbb{F}_{p^2}$ then its eighenvalues $\alpha,\beta$ are conjugated by the Frobenius automorphism, thus their order divides $p+1$ because $\alpha^{p+1}=\alpha\alpha^p=\alpha\beta=\det(\bar{g})=1$, else $\bar{g}$ has a unique eigenvalue, which must be a $\pm 1$ by $\det(\bar{g})=1$, thus $\bar{g}^2$ is unipotent and its order divides $p$. For $p=2$, in the last case, there was no reason to pass to $g^2$, as $-1=1$ in $\mathbb{F}_2$, thus $\rho(2)$ is either 1,2 or 3.
From the above two points, we conclude that for every odd prime $p$ and natural $k$, $\rho(p^k)$ divides $p^{k-1}(p-1)$, $p^{k-1}(p+1)$ or $2p^k$. All these numbers are even and bounded by $2p^k$, thus $\mathrm{lcm}\{\rho(p^k),2\} \leq 2p^k$. For $p=2$ we get that $\rho(2^k) \leq 2^{k-1}\cdot 3$.
Fix now an arbitrary natural $n$. Write $n=2^km$ for an odd $m$ and decompose $m=\prod_{i=0}^r p_i^{k_i}$. Then \begin{align*} \rho(m)= \mathrm{lcm}\{\rho(p_i^{k_i}) \mid i=0,\dots r\} \leq \mathrm{lcm}\{\mathrm{lcm}\{\rho(p_i^{k_i}),2\} \mid i=0,\dots r\} =\\ 2\mathrm{lcm}\{\frac{\mathrm{lcm}\{\rho(p_i^{k_i}),2\}}{2} \mid i=0,\dots r\} \leq 2\prod_{i=0}^r \frac{\mathrm{lcm}\{\rho(p_i^{k_i}),2\}}{2}\leq 2\prod_{i=0}^r p_i^{k_i} =2m \end{align*} and we get $$ \rho(n) = \rho(2^km) \leq \rho(2^k) \cdot \rho(m) \leq 2^{k-1}\cdot 3 \cdot 2m = 3\cdot 2^km=3n. $$
This finishes the proof that $\rho(n)\leq 3n$.