Ok - this is a classic beginner mistake I think. Performance of algorithms like grid fill depend heavily on the topology of the input. Notice the non-straight edge at the bottom (thinest) part of my surface. First, that edge was not straight, second it was not subdivided - that is - it did not contain any vertices itself. These were the key problems.
Reading the grid fill documentation made it more clear how grid fill works when you select a single closed edge loop like I was. It has to estimate where to "cut" the loop to create two opposite edges from which to then create the grid. My input topology was causing that "cut" estimation to perform poorly.
The specific answer is make sure your input topology is right for the algorithm. The more general answer is, read the docs for each function you are using, even if you don't think you need to. You don't know what you don't know.
Here is my improved grid fill: