Keep in mind that the larger the map, the longer your turn times are going to be, especially if you lots of civs. I'm playing a 256 x 256 map with 16 civs, and I'm generally waiting 5-10 minutes a turn. And that's only up to the Middle Ages! I'm guessing it will be more like 20 minutes by the time I get to the last part of the game.
Also, there's a limit of 512 cities that can be in the game, so if you make the map to large, you won't be able to fill it up. I find 256 x 256 with no cities allowed on Deserts or Tundra about right.