If curvature $\le -1$ then cut locus is is glued from the boundary of fundamental domain of $\pi_1$-action on the universal cover. If curvature $=-1$ then the fundamental domain is a convex polyhedral. The gluing maps are piecewise isometries, so the result is $(n-1)$-polyhedron, But one construct an action which gives a complicated link. Take $\mathbb Z^2$ action on hyperbolic $3$-space such that it has one fixed point on the absolute and action on its horosphere is standard action of $\mathbb Z^2$ on the Euclidean plane. (I do not see how to make a compact example.)
For the first question, in some sense the answer is "YES" if $\dim \ge 3$. I.e. there is a $G_\delta$-set in $C^\infty$-topology which satisfies your condition and dense in Gromov--Hausdorff metric.