What are your parameters for the ellipsoid?

Are you using Clark's 66, Mead, WGS 83 ...

There are too many different ellipsoid definitions to attempt to describe a specific algorithm.

If given a longitude and latitude, you have the intersection.

Unless:

Line 1: Starts at (Lat1s,Lon1s) and ends at (Lat1e,Lon1e)

Line 2: Starts at (Lat2s,Lon2s) and ends at (Lat2e,Lon2e)

If that is the case, I have found the easiest way is to convert the geographic coordinates to Lambert conformal or mercator value and then solve.