Say I have a navigation mesh in 3d space, which for simplicity's sake consists of only triangle polygons. Say the mesh is not coplanar. To construct a path we can use midpoints of edges between triangles. If we were to stop the path construction here, the character would always walk along the mesh surface when moving between two path points. However the path typically needs to be optimized to remove redundant points with ex simple stupid funnel algorithm. The issue is that all the information I could find about this algorithm seems to describe it only for two dimensional navigation meshes or for 3d navigation meshes projected onto top down view. The path points then seem to be optimized away based solely on calculating determinants in 2d space.

Now say we optimized away a point. And say the mesh is not coplanar between those two points. The character then is not moving along the mesh surface from one point to another. How does one handle this problem?

I have never implemented funnel and don't know how it works, but you can always make the mesh locally flat.

To do this around an edge, you rotate the two triangles around this edge so they preserve their angles and area, but lie on the same plane.

To do it around a vertex, you sum up the adjacent triangle angles, multiply them by PI/sum and generate a star of edges on the plane using those new normalized angles. (triangle angles become distorted, areas could be preserved by optimizing edge lengths)

For a triangle, you do the same for the one ring neighborhood of edges adjacent to its vertices. (both angles and areas become distorted - we get the same problems as with generating UV maps)

This way you could move a vertex over the surface, generating a flattened local neighborhood with smooth and minimized distortion around that point.

To look up advanced methods covering larger areas, you could lookup papers related to geodesic / intrinsic paths on meshes: https://www.cs.cmu.edu/~kmcrane/​

However, i hope and assume there is a simpler answer that that… ; )

To have a good input avoiding issues, you surely want to make your nav mesh a Delauney Triangulation at least of planar sections.
Few iterations over e queue of edge flips can do that, turning bad sliver triangles into nicer triangles with angles closer to 60 degrees.
This should already give smoother paths initially.