No. Take the sphere with $p$ the north pole, and let $U$ be the neighborhood of $0$ in $T_p S^2$ on which $\exp_p$ takes to a diffeomorphism onto $S^2$ without the south pole. Let $\gamma$ be a geodesic through the north pole, and let $p_1$ and $p_2$ be two points on $\gamma$ in the southern hemisphere. Then the shortest geodesic segment passes through the south pole, hence leaves $U$.
The difficulty is that length minimization is a global phenomenon, whereas $\exp$ is only a local diffeomorphism. Do you have additional assumptions in your problem? e.g. non-negative curvature?