Does every geometric progression contain a small remainder modulo a large prime? 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).
 A: $\newcommand{\F}{\mathbb F}$
$\newcommand{\eps}{\varepsilon}$
(As reqested by the OP, and to address @Mark Lewko's comments, here is the argument showing that the statement is true for the primes satisfying a certain condition; the missing counterpart is to prove that almost all primes satisfy the condition in question.)
Claim. Suppose that $p$ is a prime, $H<\F_p^\times$, and $a\in\F_p^\times$. If $|H|>(2\eps)^{-1}\sqrt p\log p$, then the coset $aH$ has a non-empty intersection with the interval $I:=(-\eps p,\eps p)\subset\F_p$.
Proof. Let $H^\perp<\widehat{\F_p^\times}$; that is, $H^\perp$ is the subgroup of those multiplicative characters of $\F_p$ with $H$ in their kernel. Assuming for a contradiction that $aH\cap I=\varnothing$, we have
$$ \sum_{z\in\F_p^\times} \Big(\sum_{\chi\in H^\perp}\chi(a^{-1}z)\Big)\ \Big(\sum_{g\in I} \sum_{\psi\in\widehat{\F_p}} \psi(z-g)\Big) = 0 $$
where $\psi$ runs over all additive characters of $\F_p$. The contribution of the principal character $\psi=1$ is
$$ |I| \sum_{z\in\F_p^\times} \sum_{\chi\in H^\perp}\chi(a^{-1}z) = |I|p; $$
therefore, changing the order of summation and separating the terms with $\psi=1$, we get
$$ |I|p \le \sum_{\psi\ne 1} \Big| \sum_{g\in I} \psi(-g)\Big| \sum_{\chi\in H^\perp} \Big|\sum_{z\in\F_p^\times} \chi(a^{-1}z)\chi(z) \Big|. $$
The sum over $z$ is a Gauss sum; as such, it does not exceed $\sqrt p$ in the absolute value. This gives
$$ |I|p \le |H^\perp|\,\sqrt p \sum_{\psi\ne 1} \Big| \sum_{g\in I} \psi(-g)\Big|. $$
The outer sum in the right-hand side can be written explicitly as
$$ \sum_{u=1}^{p-1} \Big| \sum_{g=-\eps p}^{\eps p} e^{2\pi i ug/p}\Big|, $$
which easily yields the (well-known) upper bound $p\log p$ for the whole sum. As a result,
$$ |I|p \le |H^\perp| p^{3/2}\log p $$
and the assertion follows in view of $|H^\perp|=(p-1)/|H|$.
