Speaking of LDO: I still haven't found the "perfect" one. I recently found this one: TPS7150
http://www.ti.com/product/tps7150
"...Because the PMOS device behaves as a low-value resistor, the dropout voltage is very low (maximum of 32 mV at an output current of 100 mA for the TPS7150)... ". Sound really good. What do you guys think?
Which LDO would you recommend?
As MarkT mentioned there is many of them with different characteristic. Some are also very sensitive on strong magnetic field etc...
If your device draws in max peaks 800mA, some voltage regulator supplies max 100 mA is far from suitable - it will burnout very quickly. In short, higher LDO value give you freedom to chose some "more common and cheaper". I would chose 4.2V battery at least, which would give maximum of 0.9V freedom of choice. As well, depends how much current battery can storage, i.e how much time you need device to run during specific period of time, until discharged, etc.
For TH components I usually use commonly found LF33CV which have max LDO of 0.45V at 800mA and much lower (0.2V, IIRC) at 100mA... If you use SMD components, there is also many choices under 1.2V LDO value.
All that depends on your overall device spec.
As well, be aware of the fact that battery rated 3.6V or 4.2V will not provide constant voltage all the time until total discharge. It will drop during time of use., which require to inspect closely the graph of the battery from its datasheet.