Let's be brutally honest folks: Teleportation is kind of a game breaker.
To make the game world feel as large as it truly is, we'll have to terminate/nerf the teleportation skill. However, to prevent the hordes of angry villages who were stranded in the middle of the desert from attacking Tiny Speck, we'll need to give them something pretty rooking awesome to make up for it. So, what could possibly replace a skill as powerful as teleportation?
Two words:
Butterfly Riding.
To ride a butterfly, first you'll need to massage so it doesn't buck you off.
Next you need to get small enough to get onto its back with the aid of of a De-Embiggenifying Potion.
Then you have to physically get onto the butterfly. (If you try this without massaging it, it'll buck you off. If you try to massage it while tiny, you'll be too small to massage it!)