Peaceful Tunneling Monsters

that have already helped create the environment your people need to survive.

You mentioned tunneling was too expensive, but having tunnels from city to city would work. What if tunnels already existed from large monsters that already created a tunnel system and your cities were scattered throughout the world using these tunnels? To get from city to city a group could move underground, even accompanied by a guard or two 'just in case'. There are many existing animals that already create tunnels, you could even use some that are nocturnal so your traveling group just needs to quietly walk by them as they sleep.