How do I Z-sort triangles for a 3D engine?

I’m building a small 3D engine for a game I’m working on. I’ve got my basics sorted: textured triangles with backface culling. However depth sorting is proving to be a difficult problem.

I’m calculating the face Z by averaging out the 3 points that make up the triangular face. The longer faces sometimes overlap the smaller faces since they have a larger Z value and therefore rise up in the depth sorted display list.

How do I fix this?

Is there a way I can use the area of the polygon to influence the depth sorting in any way? Or are there algorithms to accurately detect which triangle is above which triangle?

Cathedral rendered in a 3D program

Cathedral rendered in my 3D engine