Approximating Geodesics in a half edge DS, how can I refine my mesh to get good approximations

As you pointed out, the problem here is the discretization/subdivision of the mesh. If your mesh was made of quadrilaterals instead of triangles, the obvious subdivision strategy would be to split each quadliteral into four equally sized smaller quadliterals:

$hspace{2cm}$ $hspace{2cm}$

For any two points $P_1$ and $P_2$, Dijkstra's algorithm would yield sets of shortest paths between these points $P_1$ and $P_2$. The more you refine the discretization with this subdivision strategy, the more shortest paths you'll find between the two points. However, intuitively it is clear that for every subdivision level $linmathbb{N}$ you could pick one of these shortest paths $p_l$ such that the sequence $(p_l)_{linmathbb{N}}$ converges to the actual geodesic between $P_1$ and $P_2$ (with respect to some norm that has to be specified, for example the supremum norm).

Unfortunately, the same is not true for the standard subdivision strategy of splitting a triangle into four smaller triangles, which you have proven with your example. I believe that, at its core, the problem is that there is no way to reach the center of the triangle with a straight line from each of its edges. This can be achieved by splitting a triangle in each subdivision step into 6 smaller triangles like this:

$hspace{2cm}$ $hspace{2cm}$

I do not have a proof that this subdivision is more useful to compute geodesics with Dijkstra's algorithm, but it seems quite likely to me. I would be very interested to see what your results look like with this subdivision strategy! However, no matter what you do, in the end you may or may not end up with sets of shortest paths instead of a single shortest path. In this case you will need some kind of heuristic or additional algorithm to decide which path resembles the true geodesic most closely.