I just generated a 560x24 map in smartmap. Totally fine. Playable (at least for a while) on my 1gig ram computer.
Also, I just loaded Kr's earthmap which is odd in both dimensions: 217x119, so maps don't have to be even in either dimension.
Map scripts can only generate maps with dimensions that are a multiple of 4 in both directions, because the getGridSize function returns the number of 4x4 areas to generate in each direction. I'm unsure why they chose to do that, somewhat annoying for map scripters.
And just for kicks, I generated 1100x20 to see if the limit was 1024, and that worked and the game started, but it was pushing the limit of my available memory (terrain was black). So it looks like the limit may be higher than 1024, but you won't be playing much of that on a 1 gig memory machine.
As a final note, i've done some experimenting that showed that civ4 uses roughly 3k memory for a non-workable tile (deep ocean, mountain), and 16k memory for a workable tile, which on a 2 gig machine means you should be able to start a 350x350 ish map, or as karam desired, a 500x200 map.