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 point (say $D$) along a geodesic -- otherwise, we can move to the same point along the geodesic and then a bit more to the east. 

Moreover, the geodesic $PD$ must be orthogonal to the meridian (say $m$) through $D$. Indeed, otherwise, moving along the geodesic $PD$ from $P$ to $D$, we may pause slightly before reaching $D$ and then move othogonally to the meridian $m$ until we reach $m$. At that point in time, we will have traveled a distance $<r$ -- because locally near $D$ the sphere is flat up to effects of the second order of smallness, whereas the geodesic $PD$ being not orthogonal to the meridian $m$ creates an effect of the first order of smallness, so that effect of the non-flatness of the sphere near $D$ is negligible as compared with effect of the geodesic $PD$ being not orthogonal to the meridian $m$. So, after moving othogonally to the meridian $m$ until we reach $m$ and having thus traveled a distance $<r$, we can move a bit more to the east of the meridian $m$. 

We have the spherical triangle with vertices $N,P,D$ and the respective opposite sides of geodesic lengths $r,l,t_0$, for some real $l$. Denoting the respective angles at the vertices $N,P,D$ of the spherical triangle by $\angle N,\angle P,\angle D$, using the [sine rule][1], and recalling that $\angle D=\pi/2$, we get 
$$\frac{\sin\angle N}{\sin r}=\frac{\sin\angle D}{\sin t_0}
=\frac{1}{\sin t_0},$$
so that 
$$\sin\angle N=\frac{\sin r}{\sin t_0}\in[0,1).$$
Also, by a [supplemental cosine rule][2], 
$$\cos\angle N
=-(\cos\angle P)(\cos\angle D)+(\sin\angle P)(\sin\angle D)\cos r \\ 
=(\sin\angle P)\cos r\ge0.$$ 
Thus, $\angle N\in[0,\pi/2]$ and hence the most eastward time zone at distance $r$ from $P$ is given by 
$$\angle N=\sin^{-1}\frac{\sin r}{\sin t_0}.$$

---

**Added:** I think the above proof of the fact that the geodesic $PD$ must be orthogonal to the meridian $m$ through $D$ is rigorous enough. However, the OP requested a more formal proof of this fact. So, we can just say here that, just as in the flat plane geometry, the hypotenuse of a nondegenerate right spherical triangle is strictly longer than each of the other two sides. This is almost certainly well known, but is easier to prove than to find in the literature. Indeed, by spherical symmetry, we may assume that the vertices of the right spherical triangle are $C=(1,0,0)$, $A=(\cos p,\sin p,0)$, and $B=(\sin t,0,\cos t)$, with the right angle at vertex $C$, for some $t\in(0,\pi)$ and $p\in(0,2\pi)$. Letting $a,b,c$ denote the geodesic lengths of the sides of the spherical triangle opposite to $A,B,C$, respectively, and letting $\cdot$ denote the dot product, we see that $\cos c=A\cdot B=\cos p\sin t$ and $\cos a=C\cdot B=\sin t$. Therefore and because $t\in(0,\pi)$ and $p\in(0,2\pi)$, we have $\sin t>0$ and $\cos p<1$, so that $\cos c<\cos a$ and hence $c>a$. $\quad\Box$

  [1]: https://en.wikipedia.org/wiki/Spherical_trigonometry#Cosine_rules_and_sine_rules
  [2]: https://en.wikipedia.org/wiki/Spherical_trigonometry#Identities