If you're playing with a 256 by 256 map, it will take the whole game to move around the world if movement rates are 3 moves. Maybe the rates should proportionately be higher for bigger maps
Edit the rules.txt or whatever its equivelant is so units move more. And there might be some wonders which allow you to move specific units faster...
(Magellans Expedition, Lighthouse?)