There is a known mathematical question here: you are given a unit
vector, lying on the $(n-1)$-sphere in $\mathbb{R}^n$, $v\in S^{n-1}$, and you would
like to associate with each such vector a frame in the tangent bundle
of $S^{n-1}$ at $v$. This is a map $S^{n-1}\to \mathrm{F}S^{n-1}$ from
the sphere to its frame bundle, also known as a global section of the
frame bundle of $S^{n-1}$.
Here, the frame bundle (https://en.wikipedia.org/wiki/Frame_bundle) is
the set of all pairs $(v, (u_1, \ldots, u_{n-1}))$, of a unit vector
$v$ and $n-1$ orthonormal vectors all orthogonal to $v$, and a global section
means a map $v \mapsto (u_1, \ldots, u_{n-1})$ that is defined for all
$v$
(https://en.wikipedia.org/wiki/Section_(fiber_bundle)#Extending_to_global_sections).
Manifolds that can have such a map are known as parallelizable
(https://en.wikipedia.org/wiki/Parallelizable_manifold), and as
Wikipedia says, among the unit spheres only $S^0$, $S^1$, $S^3$ and $S^7$ are
parallelizable. So if you are looking for a way to get the orthogonal
complement $v^\perp$ of $v$ that is valid and smooth in $v$ for all
$v$, you can only do that for $n=1,2,4,8$.
For $n=3$, in fact, the proof of impossibility is simple: if the two orthogonal vectors such an algorithm would compute are $f(v)$ and $g(v)$, and both depend continuously on $v$, then $f(v)$ defines a tangent vector at $v$ to the unit sphere at the point $v$, and such a tangent vector field would contradict the hairy ball theorem (https://en.wikipedia.org/wiki/Hairy_ball_theorem).
For $n=2$, you have the map $(a,b) \mapsto (-b, a)$.
For $n=4$, you have the map
$$ (a, b, c, d) \mapsto
\begin{pmatrix}
-b & -c & -d\\
a & d & -c\\
-d & a & b\\
c & -b & a
\end{pmatrix}
.
$$
This corresponds to writing down the quaternion $w =
a+\mathrm{i}b+\mathrm{j}c+\mathrm{k}d$, where the dot product is computed as
$v_1^\top v_2 =\Re(\bar w_1 w_2)$), and the three
orthogonal vectors are $\mathrm{i}w$, $\mathrm{j}w$, $\mathrm{k}w$.
For $n=8$, you can read the answer off of the Cayley table for octonions (https://en.wikipedia.org/wiki/Octonion).
For $n=3$ and other $n$, I think the best you can do is to pick a "pole", such as
the first basis vector $e_1$, choose the rotation matrix that rotates
in the $(e_1, v)$-plane only and maps $Re_1 = v$, and use the
$(n-1)$-frame $(Re_2, \ldots, Re_n)$. The matrix $R$ can be computed
as a sequence of Givens rotations, which means its directional
derivatives should be straightforward to compute. This map has a
singularity at $v=-e_1$. This is equivalent to parallel-transporting a tangent frame at $e_1$ from $e_1$ to $v$ along the shortest path (a great circle on $S^{n-1}$) from $e_1$ to $v$, so there is a geometric interpretation to doing this.
More explicitly, write $v = \cos\theta e_1 + \sin\theta e_v$, where $e_v$ is a unit vector, $e_1^\top e_v = 0$. Then the rotation matrix in the $(e_1,e_v)$-basis is
$$R_0 = \begin{pmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{pmatrix},$$
and the change of basis from $(e_1,e_2,\ldots)$ to $(e_1,e_v,\ldots)$ is given by any orthonormal matrix $X$ such that $Xe_1 = e_1$, $Xe_2 = v$. This can be computed by QR decomposition of the $n\times(n+1)$ matrix with columns $(e_1,v,e_2,\ldots,e_n)$, and the answer is the matrix $R_0$ with the change-of-basis formula applied to it,
$$ R = X \begin{pmatrix} R_0&0\\0&I \end{pmatrix} X^{-1}. $$
This is independent of which basis $X$ is chosen, because however the QR decomposition completes the basis $R$ is just the identity on it, and it would also only fail on the two special cases, $v=\pm e_1$.
