We consider the problem of reconstructing the intrinsic geometry of a manifold from noisy pairwise distance observations. Specifically, let M denote a finite volume, diameter 1, and $d\ge2$-dimensional manifold and $\mu$ denote the normalized volume measure on M. Suppose $X_1, X_2, \cdots, X_N$ are i.i.d. samples of $\mu$ and we observe noisy-distance random variables $d′(X_j,X_k)$ that are related (in an unknown way) to the true geodesic distances $d(X_j,X_k)$. With mild assumptions on the manifold (bounded curvature and positive injectivity radius) and noisy-distance distributions (their independence and means), we develop a new framework for recovering all true distances between points in a sufficiently dense subsample of M (the denoising problem). Our framework improves on previous work which assumed independent additive noise with known, constant mean and variance. Our key idea is to design a robust Hoeffding-type averaging estimator tailored to the inherent geometric structure of the underlying data; as a result, we are able to recover true distances up to error \(O(\epsilon \log \epsilon ^{-1})\) using a sample complexity $N\asymp\eps^{-2d-2}\log\eps^{-1}$ and runtime $o(N^3)$. We will explain which properties of a manifold are necessary for the distance recovery, which suggests further extension of our techniques to a broader class of metric probability spaces. Joint work with Charles Fefferman and Jonathan Marty.