I only actually need to intersect a great circle arc i.e. the shortest path between two points, with a given small circle.
I found this tutorial for intersecting two great circle arcs, but unfortunately it doesn't cover small circles.
While an algebraic solution is possible if one assumes the earth is a sphere, we can still handle an ellipsoidal earth using Newton's method and a Esri's projection engine. The projection engine is a c style dll (pe.dll) and is bundled with the freely downloadable ArcGIS Explorer.
I think the question could be rephrased as ...
A plane is flying from NewYork to Tokyo along a great circle path - at what location(s) along it's journey is it exactly 3000 miles from San Francisco?
Think of the problem in terms of a plot of X vs Y where X is the airplane is from New York, and Y is the distance the airplane is from San Francisco. The curve can be generated using the projection engine.
The problem then becomes finding the place(s) where the curve crosses the y=3000 line.
We can make some assumptions about the curve, it is either:
Here's just a guess what the curve would look like.
By determining the slope of the curve at a guessed x, Newton's method can make an appropriate next guess, allowing it to quickly find the points where the lines intersect, or determine that they don't intersect - without knowing the internals of the projection engine.
Here is a full algebraic solution for two arbitrary small circles, using Cartesian coordinates to simplify the maths.
It's assumed the earth is a spherical, but that's fine for my purposes.
Since people are asking for a full algebraic solution, here's one that I worked through for the problem on a sphere. I am providing a link rather than a full solution since LaTeX formatting (for the math) is not provided on this site.