We introduce a fast Newton interpolation algorithm of runtime complexity $O(Nmn)$, where N denotes the dimension of the underlying downward closed polynomial space and n its $\ell^p$-degree, $p>1$. We demonstrate the algorithm to reach the optimal geometric approximation rate for analytic Bos-Levenberg-Trefethen functions in the hypercube, in which case the Euclidean degree, $p=2$, turns out to be the pivotal choice for resisting the curse of dimensionality. The spectral differentiation matrices in Newton basis are sparse, which enables realizing fast pseudo-spectral methods on flat spaces, polygonal domains, and regular manifolds. In particular, we discuss applications for high-dimensional PDEs and reaction diffusion systems on surfaces.