I am creating procedurally generated levels by stitching together "tilesets" created in a 3D modeling program such as 3DS max. Each tile consists of a 2x2x2 "section" of geometry, such as a wall, floor, corner, etc. These tiles are placed next to each other to form rooms and hallways.

After all the tiles are placed, I run a mesh simplification algorithm over the resulting geometry to reduce polygon counts for rendering and physics (and eventually NavMesh generation). The algorithm goes something like this:

1) Form groups of adjacent coplanar triangles that all have the same UV barycentric parameterizations (e.g. removing vertices wouldn't cause "warping").

2) Combine each group into a single polygon, possibly with holes.

3) Remove excess collinear vertices from the boundaries.

4) Triangulate the polygons using constrained delaunay triangulation.

The issue is that step 4) is prone to producing long skinny triangles, which is causing problems everywhere (e.g. breaking my thresholds used to detect collinearity). Can anyone provide some advice on how to approach this problem, or point me to some resources or algorithms that deal with avoiding this?

How big is your world? How big are the players and NPC? Do you really need this kind of optimization?

Are you implementing the constrained Delaunay triangulation yourself? If you do not want skinny triangles you have to introduce additional points and construct a conforming Delaunay triangulation. This means you also have to increase the triangle count relative to your constrained triangulation.

Listen to apatriarca!

Just as a footnote:
If you are having problems with floating point precision, eg. for deciding colinearity,
you can consider using exact arithmetic.
In this specific case, where you use simple geometry to represent tiles, it might be even
possible to use integer math only - assuming you use integer coordinates for vertices.

Here you can see how colinearity can be decided using +, * only.

Jonathan Shewchuk (author of the code triangle) has an excellent paper about constrained Delaunay mesh refinement here:
http://www.cs.berkeley.edu/~jrs/papers/2dj.pdf

A lot of his papers deal with this type of thing and are very readable, see here:

http://www.cs.berkeley.edu/~jrs/jrspapers.html#delref

The basic idea is to find triangles whose circumcircle contains the vertex of another triangle, then "pop" the triangle by placing a new vertex in the center of the circumcircle and recalculate the mesh locally. After repeating this process enough (and dealing with constraints and boundaries in a way detailed in the paper), the process will eventually end with a (refined) mesh that has no thin triangles.