Let $G$ be a finite group, $H$ be a subgroup of index $2$, $\phi\colon G\to G$ an automorphism. For $d\in \mathbb N$ let us say that $\phi$ is $d$-transversal to $H$ iff there is $h\in H$ such that $$ |\{g\in G\colon\, g=\phi^j(h) \text{ for some $j\in\mathbb N$}\}|\ge d $$ and $$ \{g\in G\colon\, g=\phi^j(h) \text{ for some $j\in\mathbb N$}\}\cap H = \{h\}. $$
Question: For given $a\in \mathbb N$ what is the maximal $d$ such that there is a group $G$ with $a$ elements, a subgroup $H$ of index $2$ and a $d$-transversal automorphism to $H$?
Example: If $G=(\mathbb Z/2\mathbb Z)^k$, for any subgroup $H$ of index $2$ one can easilly construct an automorphism which is $k$-transersal to it, by taking a $\mathbb Z/2\mathbb Z$-basis of $G$ such that the first basis vector is in $H$, all the other are outside of $H$, and taking an automorphism which cyclically permutes the basis vectors. This shows that $d\ge log(a)$ for infinitely many $a$'s.
My motivation is to understand whether the example from proposition 7.4. in H. Cohn, C. Umans, A group-theoretic approach to fast matrix multiplication (arxiv) could be improved. In fact the proof of it shows that for $G=(\mathbb Z/2\mathbb Z)^4$ one has $d \ge 5$.