I used to have this problem where I'd go onto the world map from a city (or otherwise), and it would take nearly two minutes to load. This occurred all the time on the world map, even before and after battles. The more time I spent on the world map, it would get progressively better, though, until I'd exit the world map for a period of time, and then it would slow down completely bad.
Now, I was using a PIII 500 Mhz, 64 MB RAM, and a nVidia TNT 8 MB VRAM (I've since upgraded to 384 MB RAM and a GeForce FX 5200 128 MB; plus I got a brand new computer since then, too); a computer with enough power to run this game. This was also pre-high resolution patch and any other major patches, for that matter. I tried nearly everything, until I found compatibility mode. I set it to Win98/ME compatibility and everything began running seemlessly. So try changing compatibility mode (right-click on the ff7.exe icon->go to "properties"->go the the "compatibility" tab->set compatibility mode to "Win98/ME" compatibility).
Of course, this fix is only relevant if you're running Windows XP. If you would have provided us with some specs, we could be of further service

.