Teleport still exists, it's in the Mobility spellbook, which you need to take at Sovereign creation.
You can also use boats, which require researching Navy as Empire, or something with a similarly self-explanatory name as Kingdom.
And, as people have said, you can alter the shape of the land around you, once you get sufficiently advanced terraforming spells. It'll cost you a lot of mana, though.