Differentiability of the distance function Suppose that $d:X \times X \to \mathbb{R}$ is a geodesic distance function on a smooth Riemannian manifold $X$ ($d$ is determined by metric tensor) and $x \in X$ is fixed. What can be said about the points in which $f:=d(x,\cdot)$ is differentiable? In particular:
-is it possible that $f$ is everywhere differentiable?
-how big the set of points in which $f$ isn't differentiable can be?
-what can be said about the structure of the set of point in which $f$ isn't differentiable (can it be a submanifold?)
I would be grateful if anybody could shed some light on these issues.
Travis's examples have a general explanation - on any complete, connected $n$-manifold, the distance function $d(p,\cdot)$ is smooth everywhere except at $p$ and on the cut locus of $p$. (You can make this conclusion by studying the exponential map - see e.g. Chapter 5.9 of Petersen's Riemannian Geometry.)

Thus your question amounts to studying the structure of the cut locus, which has been the subject of a lot of research over the last few decades; so while I'm not too familiar with it myself, you should be able to find many relevant papers online. While the picture I have in my head of the cut locus is a submanifold, I'm pretty sure there are degenerate cases where you at least lose differentiability.

If I'm interpreting the main theorem of this article correctly, you can conclude that the cut locus has Hausdorff dimension at most $n-1$, and thus that the distance function is almost everywhere differentiable, which answers the "how big" question.
For example, we can take a point $(x_0,\frac{1}{2})$ on $\mathbb{R}^2/\mathbb{Z}^2$  and geodesics $y=\pm\frac{x_0}{2}x$. Obviously, for $x_0\leqslant \frac{1}{2}$ these two lines are shortest geodesics. And if we move the point upper or lower, then the distance has a positive one-sided derivative and therefore is not differentiable at any point of $\{y=\frac{1}{2}\}$. The same for $\{x=\frac{1}{2}\}$.

Subset of singular points is not a subvariety.