I have a height map which I do collision detection and correction with. All triangles are right triangles. I find the triangle based on the x/z of the player's character and adjust the player's elevation to the highest point of that triangle. Herein lies the problem. Since the model can sometimes hang off the triangle, how do you avoid clipping with the neighboring triangles if the current triangle is lower than its neighbors? How do you avoid floating if your current triangle is higher than its neighbors? I see a few solutions to this, but none sit well with me. 1) Do collision detection for the four bottom points of the model (bounding box collisions). This is not right if the current triangle you are located on is lower or higher than the neighboring triangles. The model will clip through the higher edges of the triangles and it will float above the lower edges. 2) Position the model on the same plane (angle) of the current triangle. When the model hangs off the triangle, the neighboring triangles could be higher (which will clip) or lower (which will make the model appear to float). 3) Use larger triangles for the maps. This is sweeping the problem under the rug and could lose detail/realism on the map. I appreciate any feedback. Attached are three screenshots. Top Below Map 1 Below Map 2

You're heading in the right direction with the first solution. Instead of positioning at the highest point in the triangle you need to find the exact hight within the triangle.
First position your model above the terrain then cast rays down from each corner of the model then position the height at each corner to the terrain height where the ray intersects.
A much better discription is here
http://www.toymaker.info/Games/html/terrain_follow.html