I'll use 3-D coordinates with the $z$-axis passing through the poles, so we start at $(\cos \theta, 0, \sin \theta)$. The optimal path $\gamma$ must be a geodesic, so $\gamma$ is an arc of a great circle through $(\cos \theta, 0, \sin \theta)$. Let $\nu$ be a vector in $\mathbb{R}^3$ othogonal to $\gamma$. Since $(\cos \theta, 0, \sin \theta) \in \gamma$, we have $(\cos \theta, 0, \sin \theta) \cdot \nu = 0$.
Let the end point of this geodesic have longitude $\psi$. Then $\gamma$ must be the shortest path to the line of longitude $(-\sin \psi, \cos \psi, 0)^{\perp}$. So $\gamma$ and $(-\sin \psi, \cos \psi, 0)^{\perp}$ must meet orthogonally, which means that $(-\sin \psi, \cos \psi, 0) \cdot \nu = 0$.
So $\nu$ is a multiple of $$(\cos \theta, 0, \sin \theta) \times (-\sin \psi, \cos \psi, 0) = (-\cos (\psi) \sin (\theta),-\sin (\psi) \sin (\theta),\cos (\psi) \cos (\theta )).$$
The point of intersection of the geodesic $\nu^{\perp}$ with the line of longitude $(-\sin \psi, \cos \psi, 0)^{\perp}$ is a scalar multiple of $$(-\sin \psi, \cos \psi, 0) \times \nu= (\cos ^2(\psi) \cos (\theta),\sin (\psi) \cos (\psi) \cos (\theta),\sin (\theta)).$$
One can compute the angle between $(\cos \theta, 0, \sin \theta)$ and $(\cos ^2(\psi) \cos (\theta),\sin (\psi) \cos (\psi) \cos (\theta),\sin (\theta))$ in order to find out how long the path is. I get the answer that the length of the path is $$\sin^{-1}(\cos \theta \sin \phi).$$ That's simple enough that there is probably a better derivation; I just slogged through trig identities to get it.