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, 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$.