You could always do something like make a map with a lot of marshland in it, slowing troop walking speed significantly and restricting usable building area. You could also make a map that has a lot of trees on it which need to be chopped before large towers can be placed. Another idea you might consider is preplacing moat belonging to a player that's not on the map. Large moated areas between players would require a lot of digging and slow the game down, but would eventually allow players to build in a larger area than what they start with. You can also use varied terrain heights to create natural barriers between players that take a long time to move past.
-DOOMBRINGER-
"DOOMBRINGER, make a parking space IMMEDIATELY!"
"DOOMBRINGER declares it to be SO!"
"DOOMBRINGER, I command you to lay siege to THE ISS!"