Assume we have an arbitrary ellipsoid:
$\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}=1$
Or on it's parametric form.
We have 2 arbitrary points on the ellipse $p_1, p_2$. And there is some geodesic line passing through both. There is a midpoint $p_{mid}$ as well.
The goal is to try to approximate this midpoint somehow with the information available.
We can easily calculate the gradient $\nabla E$ where $E$ is the ellipsoid. Now, this gradient points away from the origin of the ellipse. If there is a way to make it point towards $p_{mid}$ we could simply follow the gradient down by $\epsilon$ steps, and we will have found a good approximation of the midpoint.
But I do not know if there is a simple way to compute such an approximation.
First of all, this is not an ellipse - it is an ellipsoid.
Second, by doing a search for "geodesic of ellipsoid" I found an excellent article in Wikipedia:
https://en.wikipedia.org/wiki/Geodesics_on_an_ellipsoid
In particular, the section titled "Geodesics on a triaxial ellipsoid" describes the solution discovered by Jacobi (an absolutely amazing mathematician - read his biography). It involves elliptic integrals, so your problem probably can only by solved numerically.
Your turn.