Do projections onto convex sets always decrease distances? Suppose $(M, d)$ is some $\ell_p$ metric space (not necessarily Euclidean), and $C \subseteq M$ is a closed convex set. Consider the projection function $f_C:M\rightarrow C$ defined such that:
$$f_C(x) \in \arg\min_{y \in C} d(x,y)$$
Is it the case that for all $x,y \in M$:
$$d(f_c(x),f_c(y)) \leq d(x,y)$$
i.e., is it the case that projections onto convex sets can never increase the distance between a pair of points? 
 A: No, the contractive property of the nearest-point projection is a special property of Hilbert spaces. Here is a 
counterexample in the $3$-dimensional real space with norm $\|x\|_4=(x_1^4+x_2^4+x_3^4)^{1/4}$. This is a nice norm: 
uniformly convex and uniformly smooth. The nearest-point projection onto any convex closed set is uniquely defined.
Consider the nearest-point projection $P$ onto the line $L=\{(t,t,t): t\in \mathbb R\}$. A point $x$ projects into $(0,0,0)$
if and only if the $t$-derivative of $(x_1-t)^4+(x_2-t)^4+(x_3-t)^4$ vanishes at $t=0$. Therefore, the preimage
of $(0,0,0)$ under $P$ is the surface $S_0=\{x:x_1^3+x_2^3+x_3^3=0\}$. Since the distance is translation-invariant, $P$  commutes with translations along $L$. It follows that the preimage of $(1,1,1)$ is the surface 
$S_1=\{x:(x_1-1)^3+(x_2-1)^3+(x_3-1)^3=0\}$.  
It remains to pick a pair of points on these two surfaces such that the distance between them is less than $\|(1,1,1)\|_4=3^{1/4}$.
For example, I took $a=(2^{1/3}+1,0,0)\in S_1$ and considered the distance from $a$ to the points 
$(2^{1/3}s,-s,-s)\in S_0$. The minimum is attained around $s\approx 0.93$, and it is less than $2.9^{1/4}$. 

Answering a follow-up question, I add a proof of the contractive property in Hilbert spaces. 
Let $P$ be projection onto a closed convex set $C$, and consider $a'=P(a)$ and $b'=P(b)$.
Since the segment $a'b'$ is contained in $C$, we have $\|(1-t)a'+tb'-a\|\ge \|a'-a\|$ for $t\in [0,1]$.
Therefore, 
$$0\le \frac{d}{dt}\|(1-t)a'+tb'-a\|^2\bigg|_{t=0} = 2 \langle b'-a' , a'-a \rangle  \tag{1}$$ 
Similarly, 
$$\langle a'-b' , b'-b \rangle \ge 0\tag{2}$$ 
Now consider the function
$$
d(t)=\|(1-t)a'+ta - ((1-t)b'+tb)\|^2 = \|(a'-b') + t (a-a'-b+b') \|^2
$$
which is a quadratic polynomial with nonnegative coefficient of $t^2$. From (1) and (2) we have
$$
d\,'(0) = 2 \langle a'-b' , a-a'-b+b' \rangle \ge 0 
$$
Therefore $d$ is increasing on $[0,\infty)$. In particular, $d(1)\ge d(0)$ which means 
$\|a-b\|\ge \|a'-b'\|$.
A: In negative curvature this is true.
In Bridson, Haefliger, Metric Spaces of Non-positive Curvature, Prop. 2.4 there is a partial answer.
If X is a $\operatorname{CAT}(0)$ space (e.g. $\ell_p$ with the euclidean metric), and $\pi$ is a well-defined projection to a convex, geodesic subspace, then $\pi$ is non-expanding, i.e. the distances are (non-strictly) decreasing.
