I've found that you can't underestimate the power of "doing it yourself" where surfaces are involved.
When the automatic functions fail to produce results, I've had good success with copying and pasting groups of vertices, resizing/scaling/positioning the copy relative to it's neighbor, merging the original object and the new vertices into one object, and then, 3 vertices at a time, counter clockwise, creating the faces between the vertice groups. It takes a bit longer, but it almost always does the trick, and creates no "mess".
When creating tricky things like canopy rails, turret frames, wheel wells, wingtip edges, and things of that nature for aircraft, it seems to be the ticket. I'm through with messy, unpredictable Booleans and automatic subdivides.
With your leaf, it sounds to me like you need to add some vertices towards the center of the leaf, to offset the shape a bit and add some "depth" or dimension. This might also stop the auto functions from drawing big triangles all the way across the leaf from the base to the farthest tips.
Or, try this: You
could grab all the vertices from your original elipses,
Surface/Remove Surface Only and then
Vertex/Convex Surface Object, and see if that helps. It might still create that "overtriangulated soup" you talk about, too. When creating cockpit glass panes based on the inside of canopy rails, I get extra faces I later have to remove, so that I end up with one, flat surface. If that's the case, and it gets too difficult to determine which superfluous faces to remove, then try it the way I outlined above.