Actually I only have  a vague idea of how "easy" the minimization problem should be, and how "large" the class of sets $L.$ Clearly, the optimal balance between these aspects depends on the scopes you have in mind.

The simplest sets $L$, after linear subspaces and of course spheres, are possibly the ellipsoids; although the theory for the corresponding point-set distance problem is clear, a complete solution seems not so cheap to me.

Let $A$ be a positive definite symmetric matrix of order $n$, and let $L$ be the ellipsoid $\{x\in\mathbb{R}^n\\ : \\ (Ax\cdot x)\le 1 \}$. Let $p\in\mathbb{R}^n$ not in $L$, that is  satisfying $(Ap\cdot p) > 1$. The unique minimizer $x\in L$ of the (squared) distance from $p$, $|x-p|^2$ 
satisfies
$$p-x=\lambda Ax$$
for some Lagrange multiplier $\lambda\ge0$, which is determined by the condition $x\in\partial L$, that is $(Ax\cdot x)= 1$. We have then $x=(I+\lambda A)^{-1}p$, so $Ax=(I+\lambda A)^{-1}Ap$, and 
$$1=(Ax\cdot x)=(I+\lambda A)^{-2}(Ap\cdot p)$$
If $A$ has eigenvalues $0\le\alpha_1\le\dots\le\alpha _ n$ and if the coordinates of $p$ in the spectral basis are $p_1,\dots, p _ n$. the latter equation for $\lambda$ may be written
$$1=\sum_{k=1}^n \frac{\alpha_k p_k^2}{(1+\lambda \alpha_ k)^2} $$
The RHS is indeed a strictly decreasing function of $\lambda$, vanishing at infinity, with value $(Ap\cdot p) > 1$ at $\lambda=0$, showing that it has exactly one positive solution $\lambda$, as it has to be. However, I do not know a quick solution of this equation, for all values of $(p_1,\dots p_n)$. Maybe a sub-class of ellipsoids -that is, special values of $\alpha_1,\dots \alpha_n$) do allow nice solutions.