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 it is easy to construct an action which gives arbitrary complicated link.

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

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