(Later note: This argument only works when $2$ has multiplicative order $p-1$ (mod $p$), but may give some insight to others for the general case).
This isn't really an answer, and I'm in two minds about posting it, but since no one else apart from the OP has answered, here goes: assuming that $2$ generates $A = (\mathbb{Z}/p\mathbb{Z})^{\times}$, the map $f : x \to 2^{x}$ is a bijection from $A$ to itself (where obviously $2^{x}$ is read (mod $p$) ). The question seems to amount to asking that $f$ has fewer than $\varepsilon p$ short cycles when written as a permutation ( where the meaning of short depends on the height of the tower of iterated exponentials you choose).
In trying to address this, I find it difficult to know how to generalise the question to a general finite Abelian group $G.$ If we have an arbitrary permutation $f$ of the elements of $G$, there is no a priori reason to expect $f$ to have few short cycles, (although working probabilistically, a random permutation is relatively unlikely to have short cycles)so the interaction between the additive and multiplicative structure of $\mathbb{Z}/p\mathbb{Z}$ must be playing a role. Furthermore, there does come a point at which $f^{n}$ will have plenty of fixed points, for example when $n$ is the order of the permutation $f$.
So what are the distinguishing features of the map $f$? Note that $f$ has the property that $f(x)f(-x) = 2.$ More generally, we have $f(x+y) = f(x)f(y)$ if $0 < x \leq y < x+y < p$ and $2f(x+y) = f(x)f(y)$ when $0 < x \leq y < p < x+y$. Note in particular that $x^{p-1}-1$ is a factor of $f(x)f(-x) -2.$
The question suggests another: what is the smallest value of $m$ such that $f$ has more than $\varepsilon p$ cycles of length $m?$ One way to attack that would be to show the existence of a cycle of almost maximal possible length. I don't know if there always is such a cycle.
Note added later: Sean Eberhard's answer inspired the following thought. It may work more generally, but let us consider the case where $p = 2q+1$ and $q \equiv 1$ (mod $4$) is a prime. Then $p \equiv 7$ (mod $8$), and $2$ is a quadratic residue (mod $p$), so $2$ has multiplicative order $q$ (mod $p$). If we interpret the iterated exponential $2^{*(x)}$ first as an integer, and then reduce it (mod $p$), then any fixed point has order $q$. Write $a2^{*(x)} + bq = 1.$ Then $x^{a2^{*(x)}} = x.$ Also, $2^{a*(x)} = 1.$ Since $x^{a}$ and $2^{a}$ both have odd order (mod $p$), we see that $x^{a} \equiv 2^{a}$ (mod $p$). We can't have $q|a,$ so we have $x \equiv 2 (mod $p$).$ Hence there is at most $1$ fixed point.