Roads between cities
Trade routes that can be used for travel
I could swear this was posted somewhere, but I couldn't find it...
To help exploration, most big cities should have roads between them. Walking on these roads would take much less time than through nature, making you hungry slower. You could also have a chance of encountering caravans while walking on them, allowing you to buy or sell wares, hitchhike or rob them. Of course, there would still be some remote villages disconnected from the rest of the world.