It really depend on what you ant to do... for example, If it's roman or Hellenes, I'd go to Large, but me, as I play Sweboz, and i like to roleplay tribal warfare, I play on normal size... plus, on smaller scale, you must REALLY pay attention to missiles! well, as sweboz and on normal size... Even toxotai archers are... brutal!!!
So i'd say that it's really how you enjoy it the most!

Cheers!