Most efficient way to convert from 3.5-4.2V (singe cell LiPo) to stable 3.3V for currents up to 500 mA?
I'd consider using a low-drop-out buck regulator that works almost down to the wire. Such as this one: -



When the input voltage drops to 3.3 volts, the switch inside basically remains on hence, it acts as a regulator down all the way to virtually 3.3 volts.

There are probably several examples of this tech from the usual vendors. Note that the efficiency remains pretty much above 90% from currents as low as 1 mA to over 500 mA.