Two central limit theorems for sample Fréchet means are derived, both significant for nonparametric inference on non-Euclidean spaces. The first one, Theorem 2.2, encompasses and improves upon most earlier CLTs on Fréchet means and broadens the scope of the methodology beyond manifolds to diverse new non-Euclidean data including those on certain stratified spaces which are important in the study of phylogenetic trees. It does not require that the underlying distribution $Q$ have a density, and applies to both intrinsic and extrinsic analysis. The second theorem, Theorem 3.3, focuses on intrinsic means on Riemannian manifolds of dimensions $d>2$ and breaks new ground by providing a broad CLT without any of the earlier restrictive support assumptions. It makes the statistically reasonable assumption of a somewhat smooth density of $Q$. The excluded case of dimension $d=2$ proves to be an enigma, although the first theorem does provide a CLT in this case as well under a support restriction. Theorem 3.3 immediately applies to spheres $S^d$, $d>2$, which are also of considerable importance in applications to axial spaces and to landmarks based image analysis, as these spaces are quotients of spheres under a Lie group $\mathcal G $ of isometries of $S^d$.