Best way to power sensor circuit from LiPo
I don't see an overly-compelling reason to boost up the voltage to 5V. Unless you're doing some intense time-critical math heavy calculations, I doubt 16MHz will buy you any advantage over 8MHz for the application you're describing. Single-purpose hardware can get a lot done at 8MHz.

A 3.3V linear regulator with a dropout voltage of 0.3V or less should give you pretty good performance using a 3.7V LiPo. Take a look at this graph I lifted from adafruit's website:

Let's assume your battery will be fairly small. Say 500mAh. So the 250mA load represents the red curve (0.5C). If you keep the battery between 0% and 80% discharge capacity, the battery voltage will be between 4.2 and 3.6V. A linear regulator will see efficiencies between 80% and 90%. If you can keep your current draw below 250mA, you'll see even better numbers.

One possible difficulty when working with 3.3V is parts selection. You'll need to make sure the transistors and op-amps you choose work at that voltage. If, for example, you plan to use an N-channel MOSFET to switch on an air pump that draws a few hundred milliamps from the battery, the Vgs(th) of the FET will need to be quite a bit lower than 3.3V. Otherwise its Vgs(on) will be too high to allow the pump to turn on fully.