If $G$ is a non-trivial finite group which can be generated by two non-trivial elements of prime power orders, then the answer to the question is affirmative. Let $\mathcal{G}$ be the set of all subgroups of $G$ and let $G=\langle x,y\rangle$, where $x$ and $y$ are non-trivial elements of $G$ of prime power oders. Assume $A=\lbrace H\in \mathcal{G} \;|\; x\in H, y\not\in H \rbrace$, $B=\lbrace H\in \mathcal{G} \;|\; x\not\in H, y\in H \rbrace$, $C=\lbrace H\in \mathcal{G} \;|\; x\not\in H, y\not\in H \rbrace$ and $E=\lbrace H\in \mathcal{G} \;|\; x\in H, y\in H \rbrace$. So $E=\{G\}$ and $|C|\geq 1$ as $\{1\}\in C$. It follows that either $|A|\leq |\mathcal{G}|/2$ or $|B|\leq |\mathcal{G}|/2$. 

I think (if I am not wrong) that every (if not "most" of!)  finite simple groups can be generated by two elements of prime power orders. So the question has affirmative answer for finite simple groups and $2$-generated groups of prime power orders.

-----------------------------------
UPDATE (17/January/2014): Inspired by  Russ, one can show that the question has affirmative answer for finite groups having a maximal subgroup(not necessarily normal) of prime index. Let $M$ be a maximal subgroup of $G$ of prime index $p$. If there exists an element $g\in G\setminus M$ of $p$-power order, then $G=M\langle g\rangle$. The latter holds since
$$|M\langle g\rangle|=\frac{|M||g|}{|M\cap \langle g\rangle|}.$$ Now the map $H\mapsto H\cap M$ is injective for all subgroups $H$ containing $g$. So we may assume that all $p$-power order elements are in $M$ which implies that $M$ contains all Sylow $p$-subgroups of $G$, a contradiction. This slightly improves the result of Russ, as we do not assume $M$ is normal in the group.