A sample of randomly drawn vectors are mostly perpendicular in high dimensions, as per this question. This makes sense to me.
I have a problem where given one point $v$ in $n$ dimensions, I need to sample $m$ points $\{u_i\}, \quad i=1,...,m$ such that the distribution of the angle between each $u_i$ and $v$ is uniform over $(0, \pi)$.
A simple approach would just be to fix the first $n-1$ dimensions and sample the last dimension to give the desired uniform distribution. If I want my samples to be random over every dimension, what other approaches can I take?
They cannot be "random over every dimension". To get uniformity in angular distribution, you will have to add a relation.
You don't say what you want to do with the magnitudes. All the same as $|v|$? Random with some distribution? Something else? Consequently, I describe how to get all unit magnitudes. You can scale them as suits you.
Let $\{e_i\}_{i=1}^{n-1} \cup \{v/|v|\}$ be an orthonormal basis for $n$-dimensional space. (This is relatively easy. Pick any basis. If $v$ is parallel to a basis vector, renumber them so that one is last. Otherwise, replace any of them with $v/|v|$ and apply Gram-Schmidt.) Pick a collection of latitudes $\{u_i\}_{i=1}^m$ uniformly distributed over $(0, \pi)$. Pick a collection of longitudes uniformly from the $n-1$-sphere, $\{\vec{w}_i\}_{i=1}^m$ (in the vector space spanned by $\{e_i\}_{i=1}^{n-1}$). Your sample unit vectors are $$ \sin(u_i) \vec{w}_i + \cos(u_i) \frac{v}{|v|} \text{.} $$