Since the Fibonacci numbers seem an acceptable recurrence, consider these identities:
- For $m$ even $F_{3m}=5F_{m}^3+3F_{m}$
- For $m$ odd $\ F_{3m}=5F_{m}^3-3F_{m}$
So a sixth are of the form $5x^3+3x $ and another sixth are of the form $5x^3-3x.$ There are similar results of every odd degree but I don't know about even degree. The same would be true (I think) for any sequence given by a recurrence with initial values $0,1$ and rule $a_{n+1}=ca_n+a_{n-1}$
For another kind of example, the initial values $a_0=\alpha,$ $a_1=2\alpha+2$
and rule $a_{n+1}=4(a_n-a_{n-1}).$
yield $a_n=(n+\alpha)2^n$ so, with $\alpha=6$, it would seem that $a_n$ is a square exactly for $n=4m^2-6.$
Using $5^n$ in place of $2^n$ would be even more exotic, then one also has $n=5(2m+1)^2-6$.
Looking at the the most simple cases, in terms of the order $k$ of the recurrence $L_n = a_k L_{n-1} + \cdots + a_1 L_{n-k-1}$ and/or the degree $d$ of the polynomial $f(x)$ allows some speculation on what can happen in general.
For $d=0$ we have a constant polynomial $f(x)=c.$ An integer sequence $L_n$ (given by a linear homogeneous recurrence with constant coefficients) can be periodic with in which case $L_n=c$ happens, if at all, when $n$ belongs to one or more congruence classes modulo the period $p.$ Otherwise it happens finitely often. $L_{n+6}-L_n=0$ gives period $6$ as does $L_{n+2}-L{n+1}+L_n$ (since $x^6-1=(x^2-x+1)(x^4+x^2-x-1)$). But if $L_n$ is not periodic then $L_n=c$ happens only finitely often (perhaps $k$ times at most?)
For $d=1$ we have a linear polynomial $f(x)=kx+c$. The values $L_n \bmod k$ are (eventually) periodic with a period $p \le k^d$ so $L_n \bmod k=c$ happens either finitely often or else exactly when $n$ belongs to certain congruence classes $\bmod p$ (with small exceptions, for example $2\ 3^n$ has the form $9x+0$ except when $n=0,1$.
For $k=1$ the sequence is $L_n=A\ b^n.$ What can be said then? For $f(x)=cx^s$ things are fairly clear.
With $k=2$ there is already much to think about but special cases include arithmetic progressions $An+B$ which satisfy $L_{n+2}-2L_{n+1}+L_n=0$, and more generally $(An+B)b^n$ from $L_{n+2}-2bL_{n+1}+b^2L_n=0$ Here the condition may be that the index $n$ itself is of a certain form of degree $d$ or less.
Any polynomial satisfies a recurrence, so consider $L_n=n^2(2n^2-1)$ or $L_n=n^2(2n^2-1)2^{n+1}$ either is a square for the alternate values of the Pell sequence $1,2,5,12,29,70,\cdots$
So I would wildly speculate that given two sequences $L,M$ ( given by LHRCC) we have that $L_n=M_m$ happens (with finitely many exceptions), either never or else whenever the index $n$ itself is a member of a sequence ( or one of a few sequences) given by such a recurrence.