I've run Arduinos below -40C. They do suffer a little but mostly it's external components and not the Arduino board itself. I've also broken most of the other rules in the datasheet, like using them as flight controls at this temperature.
You have a pretty specialised usage there. Average DC-DC converters won't do very well at that. One problem is the converters are optimised around some specific voltage difference and using them at basically zero voltage difference (the warm battery state) is less efficient. For example, something like this from Pololu will switch to a linear mode if the input exceeds the output and throw away energy.
Looking at the Pololu catalog, the step-up converters with 3.3V output have much worse efficiency than the higher voltages. I think that is because the unavoidable losses in the converter will be fixed voltages (like a diode drop) which are a bigger percentage of 3.3V than higher voltages.
I would build the battery bank to always require a step-down. Make it 2 cells in series. Then you're keeping the step-down regulator in its most efficient range.