What type of battery to use?
For hobby flight applications, lithium polymer ("Lipo's") generally offers the best performance from a weight-to-power or weight-to-energy ratio.  Compared with the theoretical energy density of most cells, Lipo's are quite close as they usually lack the steel casing of most other chemistries.

Their downside is a somewhat fussy nature about how they are charged (you must use a Lithium battery charger) and discharged (going below a certain voltage can severely damage the cells, turning them into a potential fire hazard when recharged), and their poor mechanical robustness, due to the aforementioned lack of a steel case.

An additional potential negative in using lithium batteries with a NiMH-designed circuit is that their voltage varies dramatically over their discharge curve, from up to 4.4 V when charging down to 3 V when fully discharged.  To fall within a 7.2 to 12 V input, a 2 or 3-cell Lipo should work.  They are usually charged at 4.3-4.4 V/cell, so a 3-cell's open-circuit voltage may be above 12 V.  If the upper limit you cite is absolute, you would be stuck with a 2-cell Lipo, which will drift well below the lower limit.

So if you're looking for an upgrade from NiMH, Lipo is the way to go.  Respect their hazards and they will provide much entertainment.