The equivalence between the two conditions is purely formal, it holds in every category of algebraic structures.
If $u$ is a non-generator and $H$ is a maximal subgroup of $G$ (by which we mean of course a maximal proper subgroup), then $\langle H \rangle = H \neq G$, hence $\langle H,u \rangle \neq G$, which implies $H = \langle H,u \rangle$ since $H$ is maximal, and therefore $u \in H$. Hence, $u$ lies in every maximal subgroup.
If $u$ is not a non-generator, choose some $X \subseteq G$ with $\langle X \rangle \neq G$ but $\langle X,u \rangle = G$. By Zorn's Lemma there is a subgroup $H$ which is maximal with the property that it contains $X$, but does not contain $u$. In fact, $\langle X \rangle$ is such a subgroup, and if $\cal C$ is a non-empty chain of such subgroups, then one can easily check that $\cup \cal C$ is a subgroup with this property. Observe that $H$ is maximal: If $K$ is a subgroup containing $H$ properly, we must have $u \in K$ and $X \subseteq K$, hence $K=G$. Hence, $H$ is a maximal subgroup not containing $u$.
Remark: Not every subgroup of a group can be enlarged to a maximal subgroup. In fact, there are groups (such as $\mathbb{Q}$) with no maximal subgroups at all. Therefore the proof is somewhat clumsy, but it works.
More generally, if $G$ is any algebraic structure, then the intersection of all proper substructures of $G$ is called the radical of $G$, and by the proof above it coincides with the set of all non-generators of $G$. If $G$ is a group, we get the Frattini subgroup. If $G$ is a left module over a ring $R$, we get its radical, which in the particular case of $G=R$ is known as the Jacobson radical. So the Frattini subgroup is really just a special case of a more general construction, whose special cases one might be familiar with.
Probably the best way to get familiar with the Frattini subgroup is to learn some of its nice properties. It is always a characteristic subgroup. If $G$ is a finite group, then $\Phi(G)$ is nilpotent. If $G$ is a finite $p$-group, then $\Phi(G)$ is the smallest normal subgroup whose quotient is elementary abelian. In this situation, Burnside's Basis Theorem states that a subset generates $G$ if and only if its image generates the $\mathbb{F}_p$-vector space $G/\Phi(G)$, which reduces the former condition to linear algebra.
Best Answer
Let $g\in\Phi(G)$ and suppose that $g$ is not a non-generator for the group. Then there exists a subset $X$ of $G$ such that $G=\langle X,g\rangle$ and $G\neq \langle X\rangle$. Then $g\notin \langle X\rangle$, otherwise $\langle X,g\rangle=\langle X\rangle=G$, contradicting our assumptions. Let $\mathscr{S}$ be the set of all subgroups of $G$ containing $\langle X\rangle$ and not containing $g$. First of all, $\mathscr{S}$ is not the empty set, because $\langle X\rangle$ belongs to it. Moreover $(\mathscr{S},\subseteq)$ is an ordered set. If we take a chain of elements of $\mathscr{S}$, and do their insiemistic union, this union also belongs to $\mathscr{S}$ and evidently is an upper bound for the elements in the chain. By Zorn's Lemma we get that $\mathscr{S}$ has a maximal element, call it $M$. Suppose $M<H\leq G$. Then $g\in H$ and $H=G$ (since $G=\langle X,g\rangle\leq \langle H,g\rangle=\langle H\rangle =H$). It follows that $M$ is a maximal subgroup of $G$, not containing $g$ , and this is absurd since we've taken $g$ in $\Phi(G)$. So $g\in \Phi(G)\leq M$, thus $G=\langle g,X\rangle=M$, absurd. We conclude that $g$ must be a non-generator of the group.
Conversely, suppose that $g$ is a non-generator and that $g$ is not an element of Frattini subgroup of $G$. Then there exists a maximal subgroup $M$ of $G$ that does not contain the element $g$. It follows that $M\neq \langle g,M\rangle$ and so, by maximality of $M$ that $G=\langle g,M\rangle$. But $g$ is a non-generator, so that $G=M$, contradicting hypothesis saying that $M$ is a maximal (hence proper) subgroup of $G$