The ardu board has one on board regulator 7805, this regulator
Well, it is a 5V regulator, but it is not a 7805. The modern Arduino boards use a LDO regulator. While 7-12V is recommended, you might find in low-current applications you can go down to 6-6.5V
what voltage battery would you choose in the following two contrasting cases?
Atmega-chip+one-LED (simple) ---versus--- Atmega-chip+Xbee+LCD+buzzer (more power-demanding)
There is a lot of "it depends" in this question. Most people would not choose a standard 9V battery, its current capacity is far to low (as compared to AAs.) Voltage is rarely as important as current capacity.
How long do you want your project to run? What is it doing when it is running? How much space do you have available? What is your budget? Can the batteries be re-charged?
Questions such as that will answer the question.