The game starts in a desolate world. How come there are inns right from the start? The sovereign/player should first focus on getting its civilization to a bare minimum. Let's say that a certain number of cities are built, or that the first city reaches a certain level. A message pops up saying: "From humble beginnings, your people is prospering! Explore the questing opportunities that can be found in inns throughout the land!"
Presto, the inns and related quests are enabled by the rebirth of civilization, and show up at random points. The player first got acquainted with empire building and can now try role-playing.
In the beginning there could be survival-related quests. For example, run-down villages can be visited. The villagers will join your empire if you give them proof that they are better off with you, like killing a nasty critter or supply them with food.
The quality of quests would improve as you improve your level of civilization. When a player finishes quests and the 'goodie huts' disappear, newer and better challenges sprout out, ready for questing.
Example of questing by civ growth (of player and AI): shacks -> inns -> frontier outposts -> castles/wizard towers...