IMO the two main question would be :
1) What microcontroller do you use? You might be able to use it at a lower voltage, maybe by decreasing the clock frequency. This would simplify your problem a gread deal.
For example if you want to use an ATMega, you may power it with as low as 1.8V if you keep the clock frequency at or below 4MHz. It will also be happy at 8MHz with much less than 3.3V. Then you can power it straight from the battery/power manager chip; not using a regulator at all will give you some significant battery gains.
2) What is the 3V3 part's lowest rated voltage? Depending on that, and the possible gains you'd make by not regulating the mcu voltage, you may be able to just discard the last drops of juice from your lipo for the same battery life (there is not that much energy left when it drops below 3.3V anyway... plus, that'd be healthier for the battery), and get rid of the step-up to 3.3V altogether. Now a LDO regulator might to the job. No switching regulator means less noise ; less parts, less power usage, less volume/weight and less price also might mean a possible bigger battery...
In order to make the right choices you'd need to specify the specifications of the parts you'd use. But using an unregulated voltage for most of the circuit, including MCU, and regulated voltage for only the 3.3V parts has many advantages.
First question- the variation in output voltage at relatively low current is probably due to transfer to a different mode of operation to increase efficiency (cycle skipping). If the circuit you have is tolerant to small changes in supply voltage, there should be no problem, if it isn't then you would have to adapt it or the regulator.
Second question- the efficiency curves indicate a small quiescent dissipation, which is normal. However, the regulator will be burning up most of the battery energy if your circuit is only drawing a couple hundred uA average at 3.3V.
It seems rather silly to be using a 2A regulator if your circuit only draws 20mA maximum. Even a linear regulator will do better (and it will be a heck of a lot cheaper and simpler). They are available with quiescent current in the 10uA range or below.
For example, a Seiko S-812C33AUA-C2NT2G would consume only about 1uA when your circuit is drawing 20uA (efficiency of 26% at 12V in/3.3V out), and 27.5% efficiency with 20mA out. The TI switcher will draw more like 1mA quiescent so the efficiency at 20uA out will be 0.5%, and at 20mA out about 80%.
So the linear regulator beats this particular switcher by maybe 4:1 assuming ~1% duty cycle, at 1/3 the price. Suggest you look at linears or more suitable switching regulators.
It's also possible to run part of the circuit on standby and fire up a big regulator when you need it, but that's probably not indicated with only 20mA draw.
Best Answer
It's much better to use switching regulators than LDOs, especially with a in-out voltage difference that you will have, because of the heat dissipation.
However one of the problems with using switching regulators for the hobbyist is that almost all of them come in surface mount packages -- of the 20,592 switching regulators currently listed on Digi-Key, just 128 come in DIP packages.
If you can get by with a maximum current draw of 1.5A on either the 5v or 3.3v rails, then I recommend the MC34063, which comes in an 8-pin DIP and costs just 62 cents from Digi-Key. (Or use a switcher for the 5.0v rail, and a LDO for the 3.3v.)
One of the drawbacks of using switching regulators is that you do have to surround it with a number of components, some of which set the voltage and current for adjustable regulators like this one. But all of these components can be easily found as through-hole parts. Here is a configuration for a 25v to 5v 1/2A step-down converter. You'll want to get an inductor with twice the current rating as your output.
If you have surface mount capabilities, then I suggest using a dual regulator like the TPS54295 in your case. It has a capacity of 2A for each rail, and comes in a fairly friendly 16-TSSOP package. It is available from Digi-Key for $2.58. The extra components needed are similar to the schematic shown above, times 2.