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).$$
Thus, the most eastward time zone at distance $r$ from $P$ is given by 
$$\angle N=\sin^{-1}\frac{\sin r}{\sin t_0},$$
at least if $r$ is small enough so that $\angle N<\pi/2$. 


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