PaulO:
Unfortunately, the Earth's distortions become difficult to manage since you suddenly need to know EXACTLY where each one is. You must consider two major factors here.
First, most of the trig routines are handled by subroutines that use what are called "telescoping series approximations" - i.e. SIN(x), even in double precision, isn't exactly accurate. (Though it is pretty good.) The errors for some angles will be very small indeed. But as a practical matter, some of the errors can get fairly big near 45 degrees. Which by odd chance happens to coincide with the area on the Earth where that surface distortion can become an issue.
Second, the Earth is not a sphere, it is an oblate spheroid, and taking the bulges and sags into account is really ugly. Fortunately, the errors of the first point I made often tend to make the non-spherical corrections immaterial. As a first approximation, don't count the differences for anything much.
Here is the part that MUST stand out in your mind... the farther apart those two points are, the greater the effects of ANY distortion, and that is true for ANY projection. You have suggested that you might have distances up to 1500 miles apart. Given that this is over 5% of the circumference of the earth (roughly speaking), you can expect distortions to really be an issue. I might consider seriously seeking that great-circle algorithm. It is a pain in the toches but it won't distort quite as quickly as some of the projections.
As to the projections, here's a real-world image of how you would make them.
For Mercator, stick a really bright neon light bulb in the Earth parallel to the polar axis. Now take a cylinder of paper. Let the light project out through the earth (I said it was a REALLY bright bulb.) The image cast on the cylinder is a Mercator projection.
For Lambert, stick a bright light bulb in the center of the earth. Now take a cone of paper and put it over the earth like a lampshade. (Hmmm... brings back vague memories of some fun parties.... but I digress). The image on the conical paper is a Lambert projection.
For Cassini-Soldner, stick the bright ligh bulb in the center of the earth. Now take a flat piece of paper and tack it to the earth at the reference coordinate. The image on that piece of paper is a Cassini-Soldner projection.
For the great circle calculation, take a circle the size of the Earth's equator. Stick it through the center of the earth so that it slices the center and the two coordinates. The chord (geometric sense of that word) of the circular slice is the shortest distance between the two points that stays on the surface of the earth.