Nowadays you can pretty easily find switchers with sub-100nA quiescent current + leakage, e.g. TPS62840 (of course, that's assuming you're at room temperature... FETs at high temperature are all crap for leakage). I note you get 80% efficiency at 1uA out on this device with a 3.6V to 1.8V stepdown config; beats the LDO by a lot, particularly if you spend a lot of your time at uA load currents.

But spin-up time... Yeah that still sucks :)