After a bit of tweaking, I managed to obtain much better results from the mesh simplification algorithm. I made two essential changes. First, I make the algorithm keep track of how far a vertex has moved from it's original position (displacement). Vertices that have already been collapsed to locations far from their original position will be less likely to be collapsed. This makes the edge collapsing look much more uniform, and simultaneously fixes the problem I mentioned earlier with normal distortion. Normals now look great!

The second major changed I made was doing multiple passes over the vertex list, slowly raising the maximum collapse cost until it matches the value given to the simplification function. This ensures that low-cost collapses will be performed before high-cost collapses.

I couldn't be happier with these results!! Finally, after two weeks, I'm done with the mesh simplification algorithm.