The A&A Terrain system required many tilesets for each of the 5 biomes, with smaller alpha channel interlocking transition tilesets to go between the main tiles.  In the beginning we were using 256x256 tiles, until programming constraints forced us to go 128.

The main challenge in doing terrain was the water.  I had to animate a bump map applied to a plane in 3DMax for 50 frames, then in photoshop do a progressive blend and brightness contrast over the overlapping frames in order for the water to look right with no fading or popping.