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 smallest 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.
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/