Teleportation is at the same time completely necessary and one of the least like features in the game, I believe I have come up with a solution that works for both sides.
Crossroads are replaced by "Waypoints", Waypoints can be built anywhere except inside a cave, mine or house. Waypoints MUST be named when created, and two Waypoints can be linked by enter their names into each other.
Once two Waypoints are linked you can select Travel to: "[Waypoint's Name]" from the other Waypoint. Once this is done you will begin to walk towards the selected Waypoint.
What makes this different from a Milestone is that when using a Waypoint you continue to walk even while logged off until you reach your goal.This would allow you to travel from city to city without having to spend the whole time clicking, you simply select a Waypoint and log off.
In order to still make normal travel viable, Waypoint Travelling would require Travel Weariness to work, kicking you out of autotravel mode if your Weariness hits 100%.
You would also be able to build objects called Signposts along the route between the two Waypoints, anyone can click on a signpost to Waypoint Travel to any of the connected Waypoints, but you cannot stop at a signpost.
Of course, your char wouldn't actually be walking through super grid after supergrid, the game would simply record how many tiles you moved since you were last on and put you that far up the trail.