The Nash-Kuiper embedding theorem states that any orientable 2-manifold is isometrically ${\cal C}^1$-embeddable in $\mathbb{R}^3$. A theorem of Thompkins [cited below] implies that as soon as one moves to ${\cal C}^2$, even compact flat $n$-manifolds cannot be isometrically ${\cal C}^2$-immersed in $\mathbb{R}^{2n-1}$. So the answer to your question for smooth embeddings is: No, as others have pointed out. I believe Gromov reduced the dimension you quote of the space needed for any compact surface to 5, but I don't have a precise reference for that.
Tompkins, C. "Isometric embedding of flat manifolds in Euclidean space," Duke Math.J. 5(1): 1939, 58-61.
Edit. Both Dean Deane Yang and Willie Wong were correct that the Gromov result is in Partial Differential Relations. I believe this is it, on p.298: "We construct here an isometric $\cal{C}^\infty$ ($\cal{C}^{\mathrm{an}}$)-imbedding of $(V,g) \rightarrow \mathbb{R}^5$ for all compact surfaces $V$." $g$ is a Riemannian metric on $V$.
