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 (16/January/2014): Inspired by the Russ Answer, one can show that the question has affirmative answer for finite groups $G$ such that $G\not=\Phi(G)$, where $\Phi(G)$ is the Frattini subgroup of $G$ which by definition is the intersection of all maximal subgroups of $G$. If $g$ is any prime power order element of $G\setminus \Phi(G)$, then $G=M\langle g\rangle$ for some maximal subgroup $M$ of $G$ so that $g\not\in M$. Now the map $H\mapsto H\cap M$ is injective for all subgroups $H$ containing $g$. So we may assume that all prime power order elements are in $\Phi(G)$ which implies that $G=\Phi(G)$.