Heres a chart from Internal Combustion Engine Fundamentals by John B. Heywood.
Its showing ISFC instead of BSFC but this will give you and idea on one of the reasons lean burn is more efficient.
When running leaner then stoich the flame speed will decrease so you will have to increase your timing advance. Now there are ways to increase flame speed when running lean burn, swirl, squish, and turbulent flow etc.
The second part of your question on octane is more dependent on a lot of variables. At light load you don't need a high octane fuel due to low amount of fuel and heat being produced. At mid load you now have to increase your octane because there is now enough fuel to make enough heat that the engine becomes heat soaked. Plus as a example say you went from a A/F ratio of 13.5:1 to 20.0:1 you just lost a lot of fuel that was pulling heat out (around 35% less fuel) during the intake and compression stroke through phase change liquid to vapor. What I have been doing on my Talon is using the turbo and inter-cooler to be able to run mid load while staying in lean burn.
The extra cool air helps cool combustion and keeps the engine from knocking.