The exact question I am interested in is the following.

Fix a small $\varepsilon\in(0,1)$ and an integer $q\ge 2$ (you may assume that $q$ is prime if it helps though I believe it shouldn't matter too much). For a large prime $P$ and an integer $a\in\mathbb Z$, define $G(a,P)=\{aq^m\mod P: m=0,1,2,\dots\}$ where the remainders are taken in the range $(-P/2, P/2)$ (i.e., with the minimal possible absolute value).

Is it true that for all primes $P$ outside of a set of density at most $\varepsilon$ (in any sense of the word "density" that is subadditive), $G(a,P)$ contains a remainder in the range $(-\varepsilon P,\varepsilon P)$ for every choice of $a\in \mathbb Z$?

However I'll be also interested in any nontrivial results in the same direction even if they fall somewhat short of a complete answer (be it affirmative or negative).