Smoothness of the closest point on a submanifold Let $(M,g)$ be a smooth Riemannian manifold, and let $S \subseteq M$ be a compact submanifold. 
Assume that for each $p \in M$, there exist a unique closest point on $S$, i.e a unique point $\tilde s(p) \in S$ such that $d(p,\tilde s (p))=d_S(p)$.
It is easy to see the map $\tilde s:M \to S$ is continuous. 

Is it differentiable? (at which points)?  If not, are there directional derivatives everywhere?
Does anything change if we assume every point has a unique minimizig geodesic to $S$? or that $M$ is complete? or both?
Edit: As shown in the example given by Willie Wong, when both conditions do not hold, $\tilde s$ does not have to be differentiable.
 A: REVISED VERSION: My original answer was at best a mess. Here is what I think is a much shorter and cleaner version:
Assume that $M$ is an open Riemannian manifold and $S\subset M$ a submanifold such that there is a unique minimal geodesic joining each $x \in M$ to $\tilde{s}(x) \in S$. Since any minimizing geodesic must be normal to $S$, there is an open subset $\Omega$ of the normal bundle of $S$ such that the exponential map $\exp: \Omega \rightarrow M$ is a smooth bijective map. The argument given by Willie below shows that there are no focal points with respect to $S$ in $M$. This implies that the exponential map is a diffeomorphism. If $\pi: N_*S \rightarrow S$ is the bundle projection, then $\tilde{s} = \pi\circ\exp^{-1}$, which is a smooth submersion.
A: When $M=\mathbb{R}^n$ and $S$ is at least $C^2$, your map $\tilde{s}$ is $C^1$ except at points $p$ where $d_S(p)={1\over\kappa(\tilde{s}(p))}$, where $\kappa$ is the largest principal curvature of $S$ at $\tilde{s}(p)$. The proof boils down to the inverse function theorem, and I don't think is much harder in the general Riemannian case (After giving it some thought, it seems that the proof in the Euclidean case does not apply readily to the Riemannian case).
Most references are concerned with the smoothness of the distance function $d_S$, but the smoothness of $\tilde{s}$ comes as a byproduct and is usually buried in the proof. See for example http://www.ams.org/tran/2007-359-12/S0002-9947-07-04260-2/
A: Consider the following: 
Take $M$ the plane with the standard (flat) metric, with the origin and the ray $[0,\infty) \times \{2\}$ removed.  
Let $S$ be the unit circle centered at the origin. Clearly for every point in $M$ there exists a unique point on $S$ that is closest to it:


*

*When $(x,y)\in M$ is such that either $x < 0$ or $y < 2$, then the closest point is $(x,y) / (x^2 + y^2)$. 

*On the other hand, when $(x,y)\in M$ is such that $x \geq 0$ and $y > 2$, then the closest point is $(0,1)\in S$. 


Clearly this mapping from $M \to S$ given by the proximal point is not differentiable on the subset $\{(0,y): y > 2\}$. 
Note however that this manifold does not satisfy the stronger version of the question where there "exists a minimizing geodesic", since the exponential map from $S$ is not surjective.   
A: The following paper discusses precisely the relation of smoothness and closest point property:
http://persweb.wabash.edu/facstaff/footer/papers/regofdistfun.pdf
See also Unexpected regularity of the distance from a $C^2$ submanifold
A: $\newcommand{\til}{\tilde}$
This is an attempt to prove rigorously that there exists an open subset $\Omega$ of the normal bundle to $S$, such that $exp:\Omega \to M$ is a bijection. This proof seems to work only when $S$ is compact.
Reminder-we assume the following:
1) For every point in $M$, there exist a unique closest point in $S$
2) For every point in $M$, there exist a unique minimizing geodesic from it to $S$
Define $\Omega=\{(s,v)\in NS|\, \,  exp_s(tv) \,  \text{ is the unique minimizing geodesic from } s \in S \text{ to } exp_s(v)  \}$
Assumption (2) (together with the fact minimizing geodesics are orthogonal to the submanifold) implies that $exp: \Omega \to M$ is a bijection. (This is the only candidate).
Assume by contradiction $\Omega$ is not open, then there exists a point $(s,v)$ in $\Omega$, and a sequence $(s_n,v_n)$ in $NS\setminus\Omega$ converging to $(s,v)$. By the definition of $\Omega$, there exists a sequnce $(\til s_n,\til v_n) \in NS$ s.t $exp_{\til s_n}\til v_n=exp_{s_n}v_n$, $|\til v_n| < |v_n|$ (the norms are taken w.r.t the metric at the different base points). since $S$ is compact, $NS$ is also compact, so we can assume $(\til s_n,\til v_n)$ is converging to some $(\til s,\til v) \in NS$. Then, continuity of $exp$ forces $exp_{\til s}\til v=exp_sv$, and continuity of the metric forces $|\til v| \le |v| $. 
The only thing we can conclude  is that $(s,v)=(\til s,\til v)$....
Actually I think $\Omega$ must be closed: If $\Omega \ni (s_n,v_n) \to (s,v)$ then $exp_{s_n}v_n \to exp_sv$. It is not hard to see that if there is a geodesic from $S$ to $exp_sv$ whose length is smaller than $|v|$, then the $v_n$ won't be the optimal lengths of geodesics from $S$ to $exp_{s_n}v_n$, for $n$ sufficiently large.

I am trying to fill in some details based on Deane's original answer (now changed) and Willie's comments, for the case when $M$ is an open Riemannian manifold and $S\subset M$ a submanifold such that there is a unique minimal geodesic joining each $x \in M$ to $\tilde{s}(x) \in S$.
Given $v \in T_xM$, Let $\alpha(\tau)$ be a path in $M$, $\alpha(0)=x,\dot \alpha(0) =v$. Given $\alpha$ there exists a unique 1-parameter family of of constant speed minimal geodesics along $\alpha$, i.e:
$f: (t,\tau) \in [0,1] \times (-\delta,\delta) \rightarrow M$  such that:
$$f(0,0) = x, f(1,0) = \tilde{s}(x), \,f(t,0) \text{ is the unique minimizing geodesic from } x \text{ to } \tilde s(x),$$ $$ f(0,\tau)=\alpha(\tau), \, f(t,\tau) \text{ is the unique minimizing geodesic from  } \alpha(\tau) \text{ to }  \tilde s(\alpha(\tau))$$
Notice, that the associated Jacobi field is $J(t)=\frac{\partial f}{\partial \tau} (t,0)$, and that $\tilde s(\alpha(\tau))=f(1,\tau)$, hence 
$$\frac{d}{d\tau}|_{s=0}\tilde s(\alpha(\tau))=\frac{\partial f}{\partial \tau} (1,0)=J(1)$$
The Jacobi field $J(t)$ satisfies $J(0) = \dot \alpha(0)=v$. We would like to show that $J(1)$ is in fact the directional derivative of $\tilde{s}$ in the direction $v$. A-priori, $J$ might depend on the chosen path $\alpha$ which represents $v \in T_xM$. (Note that $J(1)$ depends on $f(1,\tau)=\tilde s(\alpha(\tau))$).
In order to do so we will show $\frac{DJ}{Dt}(0)$ is determined only by $v$. (Since a Jacobi field $J(t)$ is uniquely determined by $J(0),\frac{DJ}{Dt}(0)$ this finishes the proof of independence).
We can represent the family $f$ via the exponential map as follows: $$f(t,\tau)=exp_{\alpha(\tau)}\big(tv(\tau)\big) $$
$$\frac{DJ}{Dt}(t)=\frac{D}{Dt}\frac{\partial f}{\partial \tau} (t,0)=\frac{D}{D\tau}\frac{\partial f}{\partial t} (t,0)$$
Note that,
$$\frac{D}{D\tau}\frac{\partial f}{\partial t} (t,\tau)=\frac{D}{D\tau}d(exp_{\alpha(\tau)})_{tv(\tau)}(v(\tau)),$$
So
$$ \frac{DJ}{Dt}(0)= \frac{D}{D\tau}d(exp_{\alpha(\tau)})_0(v(\tau))|_{\tau=0}=\frac{D}{D\tau}(v(\tau))|_{\tau=0}=\frac{Dv}{D\tau}(0)$$
Here I am stuck. How can we show $\frac{Dv}{D\tau}(0)$ depends only on $v$ (and not on $\alpha$)?
Other points that need clarification:
1) Demonstrate linearity in $v$:
For a function to be differentiable, the directional derivatives needs to be linear in their arguments. Of course, since Jacobi equation is linear, and we know $J_v(0)=v$ (which is linear), then if we could show $\frac{DJ_v}{Dt}(0)$ depends linarly on $v$ we were done.
2) Finally, linear behaviour of the directional derivatives does not in general imply differentiability. 
