Average distortion embeddings
This is a nice question. I don't know of approximation algorithms, but the known hardness results for approximating minimum distortion (and related problems such as metric labeling) should also show that $\epsilon^2$ is hard to approximate.

The reason is that they give a reduction from an NP-hard problem such that in the YES case the distortion is $O(1)$ and in the NO case the distortion is $\Omega(k)$ for at least a constant fraction of the edges. Hence, in the YES case $\epsilon^2$ will be a factor $k$ smaller than in the NO case. For details, see for instance the paper by Khot-Saket: www.cs.cmu.edu/~rsaket/pubs/approx.pdf

I'm not exactly sure which hardness factor follows from their paper, but it shouldn't be difficult to figure out. (I would guess at least the $\log^c(n)$ factor that you get for metric labeling should follow.)