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 all finite groups $G$. Let $\Phi(G)$ be the Frattini subgroup of $G$ which by definition is the intersection of all maximal subgroups of $G$. Note that $G\not=\Phi(G)$, as $G$ is finite and it has at least one maximal subgroup. 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)$, a conradiction, since a finite group can be generated by its Sylow subgroups.
SECOND UPDATE(16/January/2014) I found a gap in the above proof (Update), why $G=M\langle g\rangle$? It may not hold in general. So the answer of the question is still open for myself in general. Sorry!!