Too long for a comment.

We can simplify the proposed inequality as follows.

Put $F=\sum_{i=1}^n f_i^2$, $G=\sum_{i=1}^n g_i^2$, and $H=\sum_{i=1}^n f_ig_i$. Remark that $H\ge 0$ and
$$\|\nabla f\|^2_2=\sum_{i,j=1}^n (f_i-f_j)^2=\sum_{i,j=1}^n f_i^2+f_j^2-2f_if_j=$$ $$2nF-2\sum_{i=1}^n f_i\sum_{j=1}^n f_j=2nF-2\sum_{i=1}^n f_i\cdot 0=2nF.$$

Similarly,

$$\|\nabla g\|^2_2=\sum_{i,j=1}^n (g_i-g_j)^2=2nG.$$

Let $\operatorname{dist}$ be Euclidean distance. Then

$$2(\operatorname{dist}(\nabla{f},\nabla{g}))^2-2(\operatorname{dist}(f,g))^2=$$
$$\sum_{i,j=1}^n \left(|f_i-f_j|-|g_i-g_j|\right)^2-2\sum_{i=1}^n (f_i-g_i)^2=$$
$$\sum_{i,j=1}^n (f_i-f_j)^2+(g_i-g_j)^2-2|f_i-f_j|\cdot|g_i-g_j|-2\sum_{i=1}^n f_i^2+g_i^2-2f_ig_i=$$
$$(2n-2)(F+G)-2\sum_{i,j=1}^n |f_i-f_j|\cdot|g_i-g_j|+4H.$$

So we have to show that

$$(n-1)(F+G)+2H\ge\sum_{i,j=1}^n |f_i-f_j|\cdot|g_i-g_j|=S.$$

Applying Cauchy-Schwartz inequality, we can obtain a bit weaker result. Namely,
we have

$$S=\sum_{i,j=1}^n |f_i-f_j|\cdot|g_i-g_j|\le \left(\sum_{i,j=1}^n (f_i-f_j)^2\right)^{1/2}\left(\sum_{i,j=1}^n (f_i-f_j)^2\right)^{1/2}=2n\sqrt{FG}.$$

On the other hand, since $H\ge 0$, by the inequality between arithmetic and geometric means,

$$(n-1)(F+G)+2H\ge 2(n-1)\sqrt{FG}.$$

We can try to improve our bound as follows. Assume that $f$ and $g$ are non-zero,
$0\le\alpha\le\tfrac {\pi}2$ be the angle between vectors $f$ and $g$, and $\nabla\alpha$ be the angle between vectors $\nabla f$ and $\nabla g$. Then $H=\sqrt{FG}\cos\alpha$ and

$$S=\sqrt{\|\nabla f\|^2_2\|\nabla g\|^2_2}\cos\nabla\alpha=2n\sqrt{FG}\cos\nabla\alpha.$$

So it suffices to show that

$$2(n-1)+2\cos\alpha\ge 2n\cos\nabla\alpha.$$

This inequality holds at least when $\alpha=0$, because in this case vectors $f$ and $g$ are collinear, so the vectors $\nabla f$ and $\nabla g$ are collinear too and hence $\nabla\alpha=\alpha=0$.

3more comments