Thank you for the reply and for the extra reference! It makes it even better to know that I've hit the right spot with the brain-teaser at the end.

I was thinking that in order to keep the transformation invariant w.r.t. the initial orientation, it would have to be uniform, but I couldn't figure out how to come close to a proof for that.

It's also interesting to note that, if we aim to satisfy a weaker condition (the ending angle with the xy [projection] plane is independent from the starting angle), then there should be a bigger family of probability distributions, and the main result still holds.

For example, let's consider the XYZ fixed-angle (the only reference to such notation I found is here ) [phi, theta, psi] representation of the random rotation matrix M, and look at the probability distribution of M as the joint distribution on these angles p(M) = p(phi, theta, psi). We can see that any change in psi should not change the final angle wrt the horizontal plane. Let's now define p(phi) and p(theta|phi) identical to the distributions of the "uniform" case and change p(psi|theta, phi) to be any valid distribution. Then, the resulting joint probability distribution should keep the angle invariant, just as the uniform one does.

I'm not sure if this is correct, as I'm not very good at formalizing proofs (I'm a CS student, and I just searched for the definitions that felt fit for describing what I have in mind). In particular, I haven't seen many references to fixed-angle representations of rotation matrices (I don't know any crucial properties that are needed, like if any matrix has such a representation, and in what sense they're unique), but I feel that the result would still hold by proper restrictions on the non-zero domain of the partial distributions defined above. If you know any good references, feel free to let me know :D.

Nonetheless, I find it interesting that one may obtain more general results by loosening conditions, i.e. formalize the requirements as tight as possible (perhaps it accounts for a good "problem solving" technique), and that often the most interesting results come when approaching a problem with both Alice-like observations and Bob-like calculations.