What you are looking for is what is called the great circle distance: the shortest curve connecting two points on the surface of a sphere is given by traveling along the (there will be exactly one unless the points are polar opposites) arc of the great circle (that is, the circle of radius R) connecting them. So you do need to find an arc length but it is easy to do this without invoking calculus if you know about the dot product. Suppose the two points on the circle are represented by the vectors v and w. If v*w denotes the dot product of these two vectors, then the angle between them will be arccos(v*w/R^2) (we divide by R^2 since v and w have length R). Assuming this is in radians, to get the length of the arc connecting them we just multiply this angle by R to get R*arcos(v*w/R^2).
We are quite lucky that there is such a simple formula. For most manifolds, the curves that minimize distances are not very easy to find since it involves solving a non-linear differential equation (the geodesic equation). The fact that the sphere is so symmetric helps in this case, and you can maybe convince yourself that an arc of a great circle minimizes distance.
You may find this wikipedia article interesting: http://en.wikipedia.org/wiki/Geodesic.