Latitude and longitude values are basically vectors in spherical coordinates, usually given without the radius of the Earth.
Let's say you have a 2D circle, and you have two vectors to the edge of that circle. You want to find the distance along the edge of the circle between the heads of those two vectors -- this is called the arc length. In order to do that, you need to know the angle $\beta$ between the two vectors and the radius $r$ of the circle:
$$d=r\beta$$
An easy way to find the angle between two vectors is to use the dot product:
$$\cos \beta = \frac{\vec a \cdot \vec b}{|\vec a| |\vec b|}$$
This formula holds for vectors in 2-space as well as vectors in 3-space.
The goal now is to figure out what the two vectors should be in Cartesian coordinates. bgins' answer has this formula:
$$
X(\theta,\phi)
=\left[\matrix{x\\y\\z\\}\right]
=\left[
\matrix{
r\cos\phi\cos\theta\\
r\cos\phi\sin\theta\\
r\sin\phi
}\right]
=r\left[
\matrix{
\cos\phi\cos\theta\\
\cos\phi\sin\theta\\
\sin\phi
}\right]
$$
Now you just take two of these vectors and put them into the equation for the angle:
$$\vec a = r\left[
\matrix{
\cos\phi_a\cos\theta_a\\
\cos\phi_a\sin\theta_a\\
\sin\phi_a
}\right]$$
$$\vec b = r\left[
\matrix{
\cos\phi_b\cos\theta_b\\
\cos\phi_b\sin\theta_b\\
\sin\phi_b
}\right]$$
$$\vec a \cdot \vec b = r^2 (\cos\phi_a\cos\theta_a\cos\phi_b\cos\theta_b +
\cos\phi_a\sin\theta_a\cos\phi_b\sin\theta_b +
\sin\phi_a\sin\phi_b)$$
$$=r^2(\cos\phi_a\cos\phi_b[\cos\theta_a\cos\theta_b + \sin\theta_a\sin\theta_b] +
\sin\phi_a\sin\phi_b)$$
$$=r^2(\cos\phi_a\cos\phi_b\cos(\theta_a-\theta_b)+\sin\phi_a\sin\phi_b)$$
It's easy to see that the magnitude of each vector is $r$, so the final formula is:
$$\cos \beta = \frac {r^2(\cos\phi_a\cos\phi_b\cos(\theta_a-\theta_b)+\sin\phi_a\sin\phi_b)}{r^2}$$
$$\beta = \cos^{-1}(\cos\phi_a\cos\phi_b\cos(\theta_a-\theta_b)+\sin\phi_a\sin\phi_b)$$
$$d=r\beta=r\cos^{-1}(\cos\phi_a\cos\phi_b\cos(\theta_a-\theta_b)+\sin\phi_a\sin\phi_b)$$