Write $t,p,t_0,P$ instead of $\theta,\psi,\theta_0,p$, respectively.
In view of the condition $r<d(N,P)$, you probably meant that $t_0\le\pi/2$ (where $t_0=d(N,P)$ is the angle between the vectors $N$ and $P$). So, assume that $0\le t_0\le\pi/2$.
It is clear that we have to move to our destination along a geodesic -- otherwise, we can move to the same point along the geodesic and then a bit more, to get a bit more to the west. So, the restriction $L(\gamma)=r$ is $|a\times b|=\sin r$, where $|\cdot|$ is the Euclidean norm in $\mathbb R^3$, $\times$ is the cross product, $a:=(\sin t_0,0,\cos t_0)$, $b:=(\sin t\cos p,\sin t\sin p,\cos t)$, and $(t,p)\in[0,2\pi]\times[0,\pi]$ are the spherical coordinates of our destination point.
So, for given $t_0\in[0,\pi/2]$ and $r\in(0,t_0)$, we have to minimize $t$ subject to the conditions $|a\times b|=\sin r$ and $(t,p)\in[0,2\pi]\times[0,\pi]$. This minimization can be done in closed form by switching to the cartesian coordinates. Here is this minimization in Mathematica:
