Remember that at a full charge these battery packs will be putting out a higher voltage. The 7.4 volt pack will be running at 8.4 on full charge and around 6.6 when fully discharged and actually not recommended as it will drop below 7. Your 11.1 volt pack will be about 12.6 volts (like a Car battery that has been sitting unloaded) at full charge and 9.9 volts at full discharge. Since the 7.4 volt pack could cause problems with the regulator dropping out and not providing the full 5.0 volts, you should go with the 11.1 volt pack, but you run into the problem of heat on the boards regulator.
The fix for this is to dissipate that heat elsewhere, but how? This again is simple, use two regulators in tandem to disipate part of the heat on board (internal regulator) and some elsewhere (external regulator). All you need to do is build the external regulator circuit (very basic you can find plans online) with a LM7808 regulator. The 7808 will drop the output of the three cell pack to 8 volts which is above the minimum for the Arduino board and the internal regulator will drop it down to 5.0 volts to power the microcontroller. There is very little efficency penalty in doing this, it simply move some of the heat away from the on-board regulator. You will also want to make sure that your power cuts off when the battery voltage drops below 9.9 (ideally 10.0) as going lower will over-discharge your battery and that is around the drop out voltage of the 7808 regulator anyway.