I stumbled across the following problem: for a general non-degenerate 3D vector $\vec{r} = (x,y,z)$ find a perpendicular vector $\vec{v}$ (so $\vec{v} \cdot \vec{r} = 0$). For simplicity, since we assume that $\vec{r}$ is non-degenerate, we might as well assume that $|\vec{r}| = 1$.
Actually, this problem can be simplified even further: for a given unit vector $\vec{r} = (x,y,z)$ find any non-degenerate, linearly independent (from $\vec{r}$) vector $\vec{v}$ (then we can do a cross product $\vec{r} \times \vec{v}$ and get a perpendicular vector). I will therefore not make a distinction between finding any linearly independent vector and a perpendicular vector, since the latter can be formed by crossing the former with the original vector.
In 2D, this has a simple solution: for $\vec{r} = (x,y)$ an obvious vector parallel to this is $(-y,x)$ and it is unique (up to a constant multiple). In 3D, despite there being a whole 2D linear space of perpendicular vectors, finding any of those is "harder".
I'll demonstrate why it's problematic to come up with a "general" but "nice"${}^{(*)}$ formula: let's say $\vec{r} = (x,y,z)$. Then $\vec{v} = (-y, x, 0)$ surely is perpendicular to $\vec{r}$. While it is true that $\vec{r} \cdot \vec{v} = 0$ always, $\vec{v}$ turns out to be degenerate if $\vec{r} = (0,0,1)$. The same problem appears whichever two coordinates you choose to flip and set the third to zero, because in each case you're making a gamble: "I bet the original vector isn't in that direction", but the thing is...what if it is? Even if you choose to linearly) scramble the coordinates, like $\vec{v} = (z, 2y, x-y+3z)$, there's always a vector for which this new $\vec{v}$ is either degenerate or parallel to it. Even if we propose $\vec{v} = (f(x,y,z), g(x,y,z), h(x,y,z))$, some three (in general nonlinear) functions of $x,y,z$, this still doesn't have a general solution.
Is this really an impossible task?
${}^{(*)}$: about "niceness" of such formula: sure, we can always say: $$ \vec{v} = \begin{cases} (1,0,0); \quad &\vec{r} = (0,0,\pm 1) \\ (-y,x,0); \quad &\vec{r} \neq (0,0,\pm 1) \end{cases} $$ but I wouldn't consider this formula "nice", as it contains a cases evaluation and obviously deems the (0,0,1) direction "special".
If whatever tentative definition of "nice" should imply that $\vec{r} \mapsto \vec{v} = \vec{v}(\vec{r})$ is continuous then this is impossible to achieve for all $\vec{r} \in \mathbf{R}^3 - 0$.
As you mention, the distinction between linearly indepedent and orthorgonal is not important: in $\mathbf{R}^3$ you can take the cross product, more generally you can take the projection $\vec{v} - \frac{\vec{v} \cdot \vec{r}}{\vec{r} \cdot \vec{r}} \vec{r}$. As you also mention, we can restrict to $|\vec{r}| = 1$: if there is a construction that works for all of $\mathbf{R}^3 - 0$ then it works on $S^2$, conversely $\vec{v} = \vec{v}(\vec{r}/|\vec{r}|)$ extends to all of $\mathbf{R}^3 - 0$.
But if we are looking for a continuous choice of $\vec{v} \in \mathbf{R}^3 - 0$ for each $\vec{r} \in \mathbf{R}^3 - 0$ with $\vec{v} \cdot \vec{r} = 0$, this is exactly ruled out by the hairy ball theorem. More generally, such a continuous choice is possible on $\mathbf{R}^n - 0$ exactly when $n$ is even. A "nice" construction for any $\mathbf{R}^{2n} - 0$ is described in the linked wikipedia article: apply the $(x, y) \mapsto (-y, x)$ map to each of $n$ pairs of coordinates.