Let's say your sphere is centered at the origin $(0,0,0)$.
For the distance $D$ from the origin of your random pointpoint, note that you want $P(D \le r) = \left(\frac{r}{R_s}\right)^3$. Thus if $U$ is uniformly distributed between 0 and 1, taking $D = R_s U^{1/3}$ will do the trick.
For the direction, a useful fact is that if $X_1, X_2, X_3$ are independent normal random variables with mean 0 and variance 1, then
$$\frac{1}{\sqrt{X_1^2 + X_2^2 + X_3^2}} (X_1, X_2, X_3)$$
is uniformly distributed on (the surface of) the unit sphere. You can generate normal random variables from uniform ones in various ways; the Box-Muller algorithm is a nice simple approach.
So if you choose $U$ uniformly distributed between 0 and 1, and $X_1, X_2, X_3$ iid standard normal and independent of $U$, then
$$\frac{R_s U^{1/3}}{\sqrt{X_1^2 + X_2^2 + X_3^2}} (X_1, X_2, X_3)$$
would produce a uniformly distributed point inside the ball of radius $R_s$.
You are essentially asking for the centre of the circle that circumscribes the triangle defined by $A, B$ and $C$. Notice this is much simpler than computing the equation of a circle, as we are working with a much simpler geometrical object: a triangle.
How do you find the circumcentre (i.e., the centre of the circumcircle)?
Find the intersection of two line bisectors of the segment of the triangle described by $A, B$ and $C$.
How can you project this point onto the sphere?
Divide by the norm of this point.
Do notice that if this circle has its centre on $(0, 0, 0)$ you can't solve this problem.
Update: more about the geodesic distance from the points to the projected circumcentre
To see that the geodesic distances to the centre of the projected circumcentre from any of the 3 points given, is equivalent to showing that the triangles described by the origin, $O$, a given point (we will refer to it as $X$, where $X$ can either be $A, B$ or $C$) and the projected circumcentre, $G$, are the same triangle.
We will refer to the circumcentre of the triangle described by the points $A, B$ and $C$ as $F$.
Notice that the segments $\overline{OG}$ and $\overline{OX}$ are of length $1$, as they are radii of the sphere. So the problem is reduced to show that all $\overline{GX}$ are of the same length.
Now, let's shift our focus to the triangle $\triangle XFG$, notice that no matter which point is $X$, the angle $\angle XFG$ is of $\frac{\pi}{2}$ radians. The segment $\overline{XF}$ is equal to the radius of the circumcircle, and all these triangles share the segment $\overline{FG}$.
So using the triangle congruent criteria of 2 equal sides and equal angle formed by 2 those sides, all these triangles are congruent. Not only this, but they are congruent and have 2 sides of equal length, so it's not hard to deduce that the third side, $\overline{GX}$, are all of the same length.
Thus, we can deduce that the geodesic distance is the same (proving that the triangles $\triangle XOG$ are congruent means that the angles $\angle XOG$ are all the same, and thus the arcs of circumference have the same length).
Best Answer
This is a problem of finding a geometric median on a sphere. While the mean provides a minimizer for the sum of squared distances (in a Euclidean setting), the $L^1$ minimum is generally not expressible in such an explicit form. For three points, the Euclidean solution is known as a Fermat point, and for four coplanar points an explicit solution is known.
The usual approach is an iterative one, using a weighted least squares minimizer while adjusting the weights to obtain the $L^1$ minimum. The basic method is called the Weiszfeld algorithm, and because of the convexity of the distance function, a suitable variant on the sphere has been conjectured to converge except for countably many initial points (though as noted, the minimizing location is not necessarily unique).
Added: Let me point out a note on the three point case by K. Ghalieh and M. Hajja, The Fermat point of a spherical triangle in The Mathematical Gazette of Nov. 1996 (pp. 561-564). Although it is "behind a pay wall", you can nonetheless take advantage of JSTOR's free-of-charge program (registration required) to read the article online (see site for details), as I have done.
The authors show that when the sides of a spherical triangle $ABC$ are sufficiently short, each less than $\pi/2$ on a sphere of unit radius (implying that they are not all on the same great circle and that no two vertices are antipodal), then a Fermat point (minimizing the sum of spherical distances to three vertices) exists, is unique, and shares some defining properties with the case of a triangle in the Euclidean plane:
$$ \angle APB = \angle BPC = \angle CPA = 120° $$