@RyanBudney: I edited the question, what I meant is that there are at least two points in $S$ realizing the distance from $s$ to $S, i.e.:$ $P_S:=\{x\in M: \exists x_1\ne x_2 \text{ such that } d(x,S)=d(x,x_1)=d(x,x_2)\}$

@WillieWong Since the closest function is continuous but not generally differentiable as shown by your example, is it at least uniformly or better, Lipschitz continuous: By the way, I also wonder if the function $\tilde{s}:M\to S$ Lipchitz, i.e. can we say can we say $d_S(\tilde{s}(p), \tilde{s}(p'))\le Kd_M(p,p') \forall p, p'\in M?$? The submanifold $S$ may or may not be compact.

perhaps only somewhat related, but are slices really different that fundamental domains when $G$ is not discrete and why we don't see the name 'fundamental domain ' when $G$ is not discrete?

Sorry, but forgot to mention the paper: On the Existence of a Fundamental Domain for Riemannian Transformation Groups Author(s): Robert Hermann Source: Proceedings of the American Mathematical Society , Jun., 1962, Vol. 13, No. 3 (Jun., 1962), pp. 489-494 Published by: American Mathematical Society Stable URL: jstor.org/stable/2034968

Just saw your question. It seems that this paper may have an answer for you? I'm yet to read the paper, but in the introduction session, the author writes: "This is just a generalization of the classical concept of fundamental domain, usually formulated for G discrete. In this work we show that fundamental domains with nice properties exist for a large class of nondiscrete transformation groups: We assume that M is a complete, connected Riemannian manifold and that G is a closed subgroup of the group of isometries of M". Sorry if this isn't helpful!

@Misha Prof; Kapovich, I just came across the question and your answer. I'm wondering if there's any such similar theorem when a Lie group $G$ acts on a Riemannian manifold $M$ properly but not necessarily freely. Can we show the existence of a fundamental domain in this case? Someone else asked this on MO: mathoverflow.net/questions/251627/…. Thank you in advance!

Thank you for your very insightful answer and also for the experiments - I was wrong then, somehow I felt it could be sufficient, but now I need to see if it's necessary! I may post another question in the future then :)

Sorry, I completely forgot to mention that I want all coefficients non-negative, honestly my mistake! Upvoted your answer anyway, but I'm going to change the question if it's okay with you? I'll certainly mention that earlier I typed the question wrong.

@IosifPinelis Thanks for bringing this to my attention, I meant $P,$ I just edited the question.