Topic title is pretty misleading. You appear to be talking about hex-based map, but actually most of the ideas do not really require hexes but work just as well in freeform map (or square, 3d, whatever). Of course this doesn't make the ideas any less worthy of consideration though!
Well that is true.. I just think things become much clearer when thought in hexes. If you have units with clear sight radiuses, or pixel defined map areas producing whet i.e. it becomes kind of abusable and annoying. (Like hiding 1 pixel outside sightrange etc)
And the size of the hexes is something I'm not able to predict, decide, guess, recommend etc. That's up to more clever people than me, knowing something about amount of players and being able to do some qualified thinking. For sure they must be smaller than in the first map however. (It was a nice way to illustrate the idea)
Bring in some more ideas folks.. I was thinking about the artillery and entrenchment mechanics of PG, of course having artillery shoot past hexes would be silly in strategus, but perhaps entrenchment could give some kind of bonus of free siege shields, movable pike defenses or the like, depending on how long, and how big the army has been waiting in a hex.
Every hex could also be given clear stats that would say
something about the terrain you can expect in a battle there. I.ex it is 40% mountainous 30% forested, contains a river etc. Basically simplified version of the factors that generate random maps. After the map has been played once, it get's saved and is never changed again.
And another idea.. a plague spreading? :-D (I'll leave that one to chadz as the ultimate trolling tool of the devs..)