I experienced huge slowdowns when playing on a 256x256 map with 16 civs in the modern era - AI turns can take upto an hour! Even calculations involved when building a harbour or an airport can take a few minutes!
However I found that this is very good if I have some work to do - I play a turn, hit space, and then I can work for at least an hour, checking from time to time that I don't get any messages from my advisors!
However, on a large map (130x130, I think) with 12 civs, it is much faster - the wait between turns is no more than a minute or two, which is acceptable to me!
I am playing on a laptop, with 128 MB RAM, 650MHz Celeron.
So to Pawe - 1 minute waits are not too bad!
I also found that the advantage of long turns is that it adds realism - you feel the responsibility of your decisions, and it does feel as if you are making decisions for 5 years ahead! Loading such games is also a pain (might take upto 5 minutes), so the reloading "cheat" is out of question - hence no easy way to 'undo' bad decisions!
Note: I checked in the Task Manager that Civ3 takes up about 35MB of real memory and 195MB of virtual memory on my computer, even though about 20MB of real memory are still unused, but during AI turns it has a 99% CPU usage. So my guess is that increasing memory won't speed it too much - the key is probably the CPU power, though I may be wrong.