If your amp isn't at least half battery by volume, rethink your design. It's a common misconception that "amp" is short for amplifier. They're actually named after what they eat.
Spelunk around in the
Thomas Distributing site, they seem to always be with the lead runners.
To get size information on all the possibilities, check out
Powerstream. Note that the most competitive markets get the best mAh capacities by size, and those would be the sizes you already know, e.g. AA.
RadioShack makes the smallest 4 x AAA plastic holder. They make their own, and here the impulse to be cheap works out wonderfully. The difference just bumps the entire rest of the field out of the Hammond J series cases.
If the 9V form factor doesn't do it for you, you can also learn how to solder your own NiMH battery packs, to fit exactly into your case and to save the density loss from plastic holders. Get tabbed cells, the others shouldn't really be soldered.
Crayton Electronics has tabbed 750 mAh AAAs for $0.69, best price I've seen. I gave up on this idea so I could sell or give away my amps, no one but you will be able to replace such a battery pack when it dies.
One can also buy battery packs, e.g. check out
BatterySpace. Same point, I wouldn't count on being able to replace such a pack years later.
If you compute power/volume ratios, you'll find that AAs outclass AAAs outclass 9V, by substantial margins. You could learn to surface mount solder and etch your own boards, and design a boost regulator that runs off a pair of AAs. Some amps do this; noise is a concern to control.