First, an important equality!
$$\begin{align*}\|a-b\|^2 &= \langle a - b, a - b\rangle \\
&= \langle a,a \rangle - \langle a,b \rangle - \langle b,a \rangle + \langle b ,b \rangle \\
&= \|a\|^2 - (\langle a,b\rangle + \langle b,a\rangle) + \|b\|^2 \\
&= \|a\|^2 - (\langle a,b\rangle + \overline{\langle a,b\rangle}) + \|b\|^2 \\
&= \|a\|^2 - 2\mbox{Re}(\langle a,b\rangle) + \|b\|^2\end{align*}$$
Now, let's attack the norm inside the sup.
$$\begin{align*}\|e^{i\theta}x - e^{i\phi}y\|^2 &= \|x\|^2 - 2\mbox{Re}(\langle e^{i\theta}x, e^{i\phi}y\rangle) + \|y\|^2 \\
&= \|x\|^2 - 2\mbox{Re}(e^{i(\theta-\phi)}\langle x, y\rangle) + \|y\|^2 \end{align*}$$
Finally, use this nice fact about complex numbers: given any complex number $\lambda$, there is some $e^{ip}$ so that $\mbox{Re}(e^{ip}\lambda) = |\lambda|$. Geometrically, we are rotating the vector $\lambda$ so that it lies on the real axis. (We could also rotate to be $-|\lambda|$...)
Put these facts together, noting that $\mbox{Re}|\langle x,y\rangle| = |\langle x,y\rangle|$, since the norm is already real!