My belief is that to make anything interesting there needs to be an interesting choice being made by the players. So the answer to how to make travel interesting is simple, provide interesting choices for the players.
Random combat encounters don't tend to provide interesting choices, but that can and should be far from the only types of "random" encounters. Many of these encounters shouldn't be combat but side quests, moral dilemas, exploration & wonder, foreshadowing, building relationships, trade, etc... And even the combat ones should offer some choice.
So for example, say they come across a caravan that was attacked and some of the people from the caravan were taken. The remaining people from the caravan plead with the PCs to escort them the rest of the way. There's a moral dilemma of whether to go after the people taken, or protect those that remain, and if the PCs own quest is time relevant possibly even to just leave everyone and continue on their way. The danger level of the monster that attacked the caravan also plays a part, if it's goblins then any level of PC should be confidant that they can "win" any fight, but if it was say an adult or young adult dragon then that calculus is less clear. Any combat here is a choice, and regardless of the choice it's going to impact NPC relationships which can come up at a future time to provide more long term consequences if desired but at the end of the day it's all about choice for the players.
I should also note that if I want a game where travel matters I would go with a quality of rest homebrew, generally being you can't get a full LR unless it's in a place built for sleeping like a home, or inn. This provides an attrition element to travel, and opens up more interesting choices. Do we risk going up to this friendly looking cottage in the woods that is clearly the home of some Hag which is dangerous but probably gets us a full LR, or do we skip it and not get the LR we want/need?
