Another factor was that although both SimCity 3k and SimCity 4 both had a maximum of 256x256 tiles for their cities, the scale was different.

A SimCity 3000 tile edge was equivalent to 64m, whereas in SimCity 4 it was 16m. The scale of the city in SimCity 3000 was bigger as a result.

Hoping to test this principle of largest possible map sizes out soon.