9V to 5V regulated or 6V to 5V regulated? Which one is more efficient?
Neither is a good choice.

As you say, the 9 V battery will be quite inefficient.  9 V batteries are pretty poor in terms of energy density, and then you're going to waste 44% of what you do get in the regulator.

4 AA batteries will make about 6 V at best, which is well below what a 7805 regulator requires as input to make a reliable 5 V out.  If you do go that route, you need a LDO (low drop out) regulator.  There are plenty available that can regulate 6 V down to 5 V.

The efficiency is decent enough with the 4 AA batteries (83%), but the problem is that you won't get the full life from these batteries.  Even a LDO needs some headroom to operate, figure 300 mV roughly, although you need to consult datasheets for the real figures.  That means your 4 batteries must supply at least 5.3 V, which is 1.33 V per cell.  There is still significant energy left in a normal AA cell at 1.33 V.  The energy you do get will be used efficiently enough, but you'll leave a lot in the battery.

So what to do?  There are several options:

Don't use 5 V.  Why do you want 5 V anyway?  Modern microcontrollers run from 3.3 V, and so does most other circuitry you connect to it.  These also tend to be more efficient in terms of computes/Joule, so you win on that account too.  4 AA into a 3.3 V LDO is less efficient at making the final target voltage, but you'll probably need less current and you'll be able to drain the batteries to their end.

Use a small switcher.  There are various small switcher chips intended for exactly this application.  Microchip makes some nice ones I've used a few times, but I don't remember the part number off the top of my head.  Check their selector guide.  With a switcher, you don't have to match battery voltage and circuit voltage anymore.  Now you can use 2 AA, which still contain more energy than one 9 V battery, you can use their energy efficiently, and you can suck them totally dry.  This together with a 3.3 V circuit would be the best approach from a power standpoint.  I have done this myself a few times.