9V is the worst choice IMHO, It has the lowest mA rating. If your goal is to maximize running time, the more mA, the longer it will last. The 9V also has a lower voltage drop at the regulator, the regulator dissipates this as heat and the efficiency goes down.
The lower voltage would be better, as less voltage is dropped at the regulator, efficiency is higher, less heat produced, less energy wasted. Higher mA ..... all this equals longer usage time before the batteries go dead.
A "standard" 7805 regulator needs a volt to a volt and a half above 5 volts to maintain a constant output. A LDO regulator can operate with much lower overhead.
Also, look over the data sheet for the regulator you end up choosing and use the proper capacitors on the input and output side of the regualtor.
Good luck!
Brian