People are confusing different topics and then drawing conclusions based on those flawed perceptions. Properly designed 512x512 maps work fine, in fact a quality 512x512 map will easily outperform smaller, poorly designed 256x256 maps. Simply stated, cpu performance in this case is tied directly to poor AI pathfinder algorithms and poor map design, not map size.
If even one unit gets stuck at a specific location on a map - including 128x or 64x maps - then its only a matter of time before 10 more units get stuck at that same spot - and then 20 and then 40. Full stop. The AI pathfinder is now calling in loops, infinite looping is a bad thing for a computer CPU. For all intents and purposes, the game (cpu handling) just became a smoking pile of shrapnel.
I've played games on large maps - versus 3 AI opponents - where each faction had produced in excess of 520+ units and the CPU was fine - the amount of RAM on my computer WAS a problem but thats my problem and not related to this topic.
OP - go ahead and make the map, I'd be more than happy to beta test it previous to the public release.