Comparison Statement I'm looking for a statement like this (and for a proof too):
Let $\gamma_1,\gamma_2:\mathbb R\to (M,g)$ two curves (parametrized by arclength) in a Riemannian manifold $(M,g)$ and let $\gamma_1(0)=\gamma_2(0)$ and $\gamma_1'(0)=\gamma_2'(0)$. Now the claim is as follows:
Let $|D_t\gamma_1'(t)|>|D_t\gamma_2'(t)|$ for all $t$ and let $s_1$ respectively $s_2$ be the times, when $\gamma_1$ respectively $\gamma_2$ leave the geodesic ball of radius say $r$ centered at $\gamma_i(0)$ for the first time ($r$ can be small, I'm interested in a local statement).
Then $s_1>s_2$.
The statement seems to be obvious but I can't come up with a proof... Thanks for any ideas.
 A: The proposition you want seems to only be true if $r$ is allowed to depend on the curves $\gamma_1, \gamma_2$. 
To be precise, the following statement appears to be false: "Given $p \in M$, there exists some $r > 0$ such that for any $\gamma_1, \gamma_2$ satisfying your conditions, $s_1 > s_2$."
As a counterexample, let $M = \mathbb{R}^2$ with the Euclidean metric, $p$ the origin. Fix some $r$. 
Let $\gamma_2$ be the curve as follows: For $0 < t < r/2$, $\gamma_2$ is just the unit speed geodesic along the $x$-axis. Then, for $r/2 < t < 3r/4$, $\gamma_2$ makes a half-circle around the point $(r/2, r/4\pi)$; finally, for $t > 3r/4$, $\gamma_2(t)$ is the path $(5r/4 - t, r/2\pi)$.
Now let $\gamma_1$ be the same curve on $0 < t < r/2$, but cause $\gamma_1$ to trace out a (much tighter) full circle for $r/2 < t < 3r/4$ (this time around the point $(r/2, r/8\pi)$), and then continue out along the $x$-axis. 
$\gamma_1$ leaves the ball of radius $r$ at time $5r/4$, whereas $\gamma_2$ leaves at some much later time. Now my $\gamma_1$ doesn't satisfy $|D_t \gamma_1'(t)| > |D_t \gamma_2'(t)|$ for $0 < t < r/2$ or for $t > 3r/4$, but it's clear that some small perturbation of $\gamma_1$ will satisfy this condition and still leave the ball earlier. (These curves aren't smooth either but again that can be fixed.)
[Edit: The rest of this answer appears to be nonsense. The computation of $L'''_i(0)$ in the proof seems to have several mistakes, and I'm not sure whether they can be fixed; consequently, I'm now agnostic as to whether the proposition below is true.]
On the other hand: 
Proposition [Edit: possibly false]: Given $p \in M$ and unit speed curves $\gamma_1, \gamma_2$ satisfying $\gamma_1(0) = \gamma_2(0) = p$, $\gamma_1'(0) = \gamma_2'(0)$, and $|D_t\gamma_1'(0)| > |D_t\gamma_2'(0)|$, it follows that there is some $R > 0$ such that for all $r < R$, $\gamma_2$ leaves the $r$-ball about $p$ before $\gamma_1$.
Proof [Edit: flawed]: Fix normal coordinates around $p$. For $i \in \lbrace 1, 2 \rbrace$ and each $t > 0$ define
$$
L_i(t) = \int_0^t \langle \gamma_i'(s), \partial_r(s) \rangle ds.
$$
As long as $t$ is small enough, $L_i(t)$ is the distance from $p$ to $\gamma_i(t)$. (Here $\partial_r(s)$ is the unit vector in the radial direction at $\gamma_i(s)$.) It's easy to compute
\begin{align}
L_i'(t) &= \langle \gamma_i'(t), \partial_r(t) \rangle \\
L_i''(t) &= \langle D_t \gamma_i'(t), \partial_r(t) \rangle + \langle \gamma_i'(t), D_t \partial_r(t) \rangle.
\end{align}
In particular the second formula implies $L_i''(0) = 0$, so that $L_1$ and $L_2$ agree to second order at $t = 0$. I claim that $L_1'''(0) < L_2'''(0)$, from which the claim follows.
To prove the claim I want to get a nice formula for $L_i'''(0)$. I first remark that $D_t \partial_r(0) = 0$. (This is a computation, but intuitively, $\gamma_i$ is going out from $p$ in the radial direction to first order at $t = 0$, so $\partial_r$ isn't changing to first order.) But then
$$
D_t \langle \gamma_i'(t), D_t \partial_r \rangle \big|_{t=0} = \langle \gamma_i'(t), D_t^2 \partial_r \rangle \big|_{t=0} = \langle \partial_r, D_t^2 \partial_r \rangle \big|_{t = 0} = \langle D_t \partial_r, D_t \partial_r \rangle \big|_{t = 0} = 0. 
$$
(Here I use $D_t \partial_r (0) = 0$ and $\langle D_t \partial_r(t), \partial_r(t) \rangle = 0$ to get rid of unwanted terms.) It follows that
$$
L_i'''(0) = \langle D_t^2 \gamma_i'(0), \partial_r \rangle = \langle D_t^2 \gamma_i'(t), \gamma_i(t) \rangle \big|_{t = 0} = -\langle D_t \gamma_i'(t), D_t \gamma_i'(t) \rangle \big|_{t=0} = - |D_t\gamma_i'(t)|^2
$$
using the fact that $\langle D_t \gamma_i'(t), \gamma_i'(t) \rangle = 0$ since $\gamma_i$ is unit speed. The condition $|D_t \gamma_1'(0) | > |D_t \gamma_2'(0)|$ now implies exactly that $L_1'''(0) < L_2'''(0)$, which is what we wanted.
A: I was finally able to answer the question. The goal is to give a Taylor expansion for the function $L$ above from mollyerin's answer: In order to fix notation, the Levi-Civita connection is denoted by $\nabla$. Pick geodesic normal coordinates centered at $p$.
By using the Gauss-Lemma we find
$$\begin{aligned}L(t) &=\int_0^t g\left(\dot\gamma(s),\partial_r(s)\right) \,\mathrm ds\\
& = \int_0^tg\left( (\mathrm d\exp_p)_{\bar \gamma(s)}(\dot{\bar\gamma}(s)),(\mathrm d\exp_p)_{\bar \gamma(s)}\left(\tfrac{\bar\gamma(s)}{\left|\bar \gamma(s)\right|_g}\right)\right)\,\mathrm ds\\
& =  \int_0^tg\left( \dot{\bar\gamma}(s),\tfrac{\bar\gamma(s)}{\left|\bar \gamma(s)\right|_g}\right)\,\mathrm ds\\
& =  \int_0^t\frac{\mathrm d}{\mathrm ds}\left|\bar \gamma(s)\right|_g\,\mathrm ds= |\bar{\gamma}(t)|_g,
\end{aligned}
$$
where $\bar\gamma = \exp_p^{-1}\circ\gamma$. We can expand
$$\bar\gamma(t)=\dot{\bar{\gamma}}(0)t+\frac{\ddot{\bar{\gamma}}(0)}{2!}t^2+\frac{\dddot{\bar{\gamma}}(0)}{3!}t^3+O(t^4)$$
and choose the coordinates such that $\dot{\gamma}(0)=\partial_1$. Since $(\mathrm d\exp_p)_0$ is the identity on $T_pM$, we find $\dot{\bar{\gamma}}(0)=\dot\gamma(0)$.
Since the Christoffel symbols vanish in $p$ (normal coordinates), we obtain $\nabla_{\dot{\gamma}}\dot{\gamma}(0)=\ddot{\bar\gamma}(0)+\dot{\bar\gamma}^i\Gamma_{1i}^j\partial_j(0)=\ddot{\bar\gamma}(0)$. For the second covariant derivative we compute (using again that the Christoffel symbols vanish in zero)
$$\nabla^2_{\dot{\gamma}}\dot{\gamma}(0)=\dddot{\bar{\gamma}}(0)+\dot{\bar\gamma}^i\partial_1\Gamma_{1i}^j\partial_j(0)=\dddot{\bar{\gamma}}(0)-\frac{1}{3}\left(R^j_{111}+R^j_{111}\right)\partial_j(0)=\dddot{\bar{\gamma}}(0)$$
The equality in the middle uses the identity
$$
\partial_l\Gamma_{jk}^i(0)=-\frac{1}{3}\left(R^i_{jkl}(0)+R^i_{kjl}(0)\right),
$$
that holds in normal coorinates and the last equality uses the symmetries of the curvature tensor.
It follows that
$$
d(p,\gamma(t))^2=|\bar{\gamma}(t)|_g^2 = t^2+\frac{1}{2}\left.g(\nabla_{\dot{\gamma}}\dot\gamma,\dot\gamma)\right|_{t=0}t^3+\frac{1}{4}|\nabla_{\dot{\gamma}}\dot{\gamma}(0)|^2t^4+\frac{1}{3} \left.g(\dot\gamma,\nabla_{\dot{\gamma}}^2\dot{\gamma})\right|_{t=0}t^4+O(t^5)
$$
and since $\gamma$ is parametrized by arc length, $\left.g(\nabla_{\dot{\gamma}}\dot\gamma,\dot\gamma)\right|_{t=0}=0$ and $|\nabla_{\dot{\gamma}}\dot{\gamma}(0)|^2=-\left.g(\dot\gamma,\nabla_{\dot{\gamma}}^2\dot{\gamma})\right|_{t=0}$. This implies
$$
d(p,\gamma(t))^2 = t^2-\frac{1}{12}|\nabla_{\dot{\gamma}}\dot{\gamma}(0)|^2t^4+O(t^5)
$$
and applying $\sqrt{1+x}=1+\frac{1}{2}x+O(x^2)$ for $x\to 0$, we obtain
$$
d(p,\gamma(t))=t-\frac{|\nabla_{\dot{\gamma}}\dot{\gamma}(0)|^2}{4!}t^3+O(t^4)
$$
which is also in agreement with the examples that have been discussed in the thread.
A: This would be true if one of the curves is a geodesic, but otherwise it is not true even in the plane.  Namely, one can send $\gamma_2$ on a circular orbit in such a way that it will never leave the disk, and take for $\gamma_1$ a spiral (or cycloid) that's spinning rapidly (with small coils) so that its second derivative will be bigger than that of $\gamma_2$, but it will gradually travel out of the disk.
