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 the westeast.
Let $|\cdot|$ denote the Euclidean norm in $\mathbb R^3$, let $\times$ denote the cross product, let $P=(x_0,0,z_0):=(\sin t_0,0,\cos t_0)\in S^2\subset\mathbb R^3$ (the starting point), $D:=(x,y,z):=(\sin t\cos p,\sin t\sin p,\cos t)\in S^2\subset\mathbb R^3$ (the unknown destination point), where $(t,p)\in[0,\pi]\times[0,2\pi)$ are the spherical coordinates of our destination point $D$.
Then the restriction $L(\gamma)=r$ is $|P\times D|=\sin r$, because the geodesic distance $d(D,P)=r$ between $D$ and $P$ is the angle between the unit vectors $P$ and $D$.
So, for given $t_0\in[0,\pi/2]$ and $r\in(0,t_0)$, we have to minimize $t$ subject to the conditions $|P\times D|=\sin r$ and $(t,p)\in[0,2\pi]\times[0,\pi]$. Perhaps, this minimization can be done in closed form by switching to the cartesian coordinates, since $$|P\times D|^2=1 - z_0^2 z^2 - 2 z_0\sqrt{1-z_0^2}\, x z -(1-z_0^2) x^2.$$