I think randomizing is the best way to let us know exploration is better than setting out some strict leveling plans. Could randomize what quests are available at that day or hour. Could randomize where you can get the quest items. Maybe some NPCs won't give you the quest but you can find the quest item. The sense of randomized quests would make it more exploration based. Maybe some NPCs aren't at the same place or even around that day, you might find them somewhere out there near a cave instead of in town.