Heard about geodesics? The two points on any surface can be connected by a geodesics. For example, if the surface happens to be a plan, the geodesics will be a straight line connecting the two points. Then the lenghth of the segment of the curve will be the distance.
Usually, for any surface, getting the geodesics amounts to solve a bunch of ODE's, which sounds like a daunting job. Fortunately, it's pretty simple to get geodesics on a sphere, which are called "grand circles". Furthermore, for any two points on the sphere of radius r, the distance can be obtained by integrating
ds^2=r^2 * (dtheta^2 + (sin(theta))^2 * dphi^2)
where (t, phi, theta) is the sphere coordinate.
So, here is what you should. First, choose your sphere coordinate system and then transform the latitudes and the longitudes to sphere coordinates. The second step is to construct a relationship between theta and phi. Notice that if your sphere system is chosen properly, this relation could be as simple as an equation for a straight line. The last step to integrate the differential relation above, which essentially is just calculating the length of a piece of arc.