The best AA cells I've seen are the GP2000s (17.5mm by 43.5mm). I watched Ed Hughey break a SAW record with one of his FE boats using them, then stay on the course to break a two-lap oval record. These cells will put out 40+ amps at high voltage...
if legal they give you a great advantage.
http://www.battlepack.com/loosecells.asp However, it sounds like you have to use alkaline cells of 1.5v each....that changes everything.
I believe that a small catamaran would be the best considering the limited power and turning requirements. It gives a small wetted area and sharp turning. What motors are allowed? With the limited power available out of the cells.....hmmm.