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)$