...1. Open "CIV4WorldInfo.xml" file located in your "C:\Program Files\Firaxis Games\Sid Meier's Civilization 4\Assets\XML\GameInfo" folder.
2. Choose the existing map size you would like to change and find the appropriate tags to edit the grid heighth and width:
"<iGridWidth>32</iGridWidth>
<iGridHeight>20</iGridHeight>"
*Each grid cell consists of 4 tiles (plots), so a 32x20 map grid is actually 128x80 plots....