I’m pretty sure a modern image-editing package can handle 16384*16384 – even at 16-bit per colour-channel (apparently, the forthcoming version of GIMP can handle images with 64-bit per colour-channel).
I’m not sure if there are any restrictions in-game for maximum slopes (would it be OK for example to have adjacent pixels with heights of 0 and 65535)? Even if there were such restrictions, the terrain-generator could smooth out those steep slopes. Also, if using an 8-bit image (256 layers) or an image with reduced area (e.g.. 1024*1024 for the small map), the terrain-generator could always apply some smoothing or even a bit of noise to spice things up. Maybe we could have a really small heightmap-image and instead of using that as the actual heightmap, it would be used to ‘seed’ the map generator (i.e. it give it hints as to where the mountains, plains and plateaus are to be placed).
Also for the town-map, it could be a 256-colour paletted bitmap (8-bit), where each colour would represent a different town (only one pixel of each non-background colour would be allowed), and there would be a text file with a list of up to 255 town-names so that you can assign a name to the town of each colour. As an alternative to using a single pixel, the towns could be a blob that represents which parts of the map they occupy so you can have things like circular towns and skinny towns (the latter are usually placed in valleys). Alternatively, if the “town’s growth potential” feature is implemented, the blob’s area could represent the growth-potential of the town (is this town capable of growing into a vast metropolis, can it only grow to a medium sized city, or will it stay a small town forever?). However, you’d have to be careful to make sure all of the area of a single colour is contiguous (i.e. no exclaves). Alternatively, the growth potential could be mentioned in the text-file with the names and we can instead use the blobs to define the initial town-area.
The resources-map and the tree and farm placement maps could be combined to that each bit of an 8-bit bitmap represents the presence of a resource. So if bit 0 represents coal, bit 1 represents iron, bit 2, forests and bit 3 farms (although farms and forests would be mutually exclsive), an area of colour #5 would be a forest with a coal-seam underneath (both the woodcutter and coal-mine industries can be placed at this spot by the map-generator). Unless we use > 8 bpp images, we’d be limited to 8 primary resource-types or landscape features – not a problem for the vanilla game, but once you start using plug-in industries, it becomes a problem.