Ah. I think I see. When more load is put on a battery, voltage drops. If you demand too much current, the voltage drops to a level you can't use. So if a 1.5v battery is rated at 5000 mAh, it could output 5A continuously for an hour, at 1.5v. But if you demand 10A (2C), it's voltage would drop, maybe to around 1.2v.
I'd love to use a lead acid battery, but it's almost 4kg :o. We'd like it to be really light. I've done some calculations for how much the servos will be able to support, and though I can't remember the exact numbers right now, I'm pretty sure this is too heavy.
Thanks so much for the help, but now I have another question. How would wiring an external power supply to the arduino mega work? Do I plug the + and ground into the headers, or do I have to buy a 2.1mm plug?
Edit:
Can NiMH batteries work at 1C? That's all I really need. Maybe I should use NiCd?