A linear regulator will do about as well as any alternative.
Options of regulator parts that are suitable (inexpensive and with low dropout voltage of under 200mV at around 400-500 mA current) include the following: TPS73633, TPS73733, TPS79533, TPS79633, LD39080DT33, LD39150PT33, MIC5353-3.3, ADP124ARHZ-3.3
Efficiency will be close to or over 90% for most of battery voltage range.
Probably 80%+ of battery capacity will be available and leaving some capacity in the battery will add usefully to battery cycle life as LiPo and LiIon batteries "wear out less" if Vbattery does not drop too low.
A buck regulator could get better efficiencies if extremely carefully designed but in many cases will not.
TPS72633 datasheet - fixed 3.3V out, <= 5.5V in. Well under 100 mV dropout at 400 mA across temperature range. About $US2.55/1 at Digikey, falls with volume.
TPS737xx datasheet up to 1A with 130 mV dropout typical at 1A.
LD39080... datasheet 800 mA, dropout OK.
You say load is 400 mA peak over short periods but <= 5 mA for 95% of the the time. You do not say what battery capacity you wish to use, but let's assume 1000 mAh capacity - not a very large battery physically and common in cellphones etc.
If 3.3V is wanted then a regulator with Vin >= 3.4V is easily achieved and 3.5V in even more so.
So what % of battery capacity do we get at 0.4 C at room temperatures? Based on the graphs below - probably over 75% at 400 mA and close to 100% at 5 mA for a 1000 mAh battery. See below.
For Vout = 3.3V and 90% efficiency, Vin = 3.3 x 100%/90% = 3.666 = 3.7V. So up to 3.7V a linear reguator gives >= 90% - which it is possible to exceed with a buck converter, but only with great care. Even at Vin = 4.0V, efficiency = 3.3/4 = 82.5%, and it does not take long for Vin to fall below this, so in most cases efficiency of a linear regulator will be close to or above 90%, while using the majority of the battery capacity.
While I feel D Pollit's figure of 3.7V for Vbattery_min is too high in this case, using a figure of 3.5V or 3.4V will provide the large majority of battery capacity and will usefully prolong battery cycle life.
Capacity as a factor of temperature and load: 400 mA = 0.4C.
The left hand graph below from a Sanyo LiPo datasheet which was originally quoted. At 0.5C discharge the voltage drops below 3.5V at about 2400 mAh or 2400/2700 = 88% of nominal capacity of 2700 Ah.
The right hand graph shows discharge at 1C at various temperatures. At 0C the voltage drops below 3.5V at about 1400 mAh but at 25C it's about 2400 mAh (as per left hand graph) so as temperature drops we can expect a substantial drop in capacity, but down to say 10C you'd expect 2000 mAh or more. That's at 1C discharge, the 400 mA = 0.4C in this example, and the 95% discharge rate of 5 mA will probably give close to full nominal capacity.