Actually I think the slowdown has to do with calculation of trade routes and borders. Right around when you see battleships, airports are being finished. An airport creates a trade route to all other cities with airports.
On a side note, I've taken to playing on huge maps and have next to no slowdown. Part of it is probably the 512 MB of RAM. The other part is probably because I always shoot for a diplomatic victory.