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.)

>So the answer to the second question is "NO".

For the first question, I think the answer is "YES" if $\dim \ge 3$.
I.e. there is a dense $G_\delta$-set of metrics which satisfies your condition.
(Your condition is open, and it seems one can construct a metric which satisfies your condition arbitrary $C^\infty$-close to a given metric...)