Walking long distances is a similiar case of pressing and holding the "move forward" button for prolonged periods of time... and the only fix to that seems to be to add some combat at steady intervals. Why just combat? I would try to figure out what all "would" an inquisitive and/or creatively built character (inquisitive, because not everyone needs to) do along their trek that would also give it a systemic flavor. Be the trek through a city or a wilderness. And I don't mean checking containers here either - game being littered with boxes to loot is one form of intense irritation because slows everything down, devalues everything you find in them, and still demands attention because "you never know".
Im quite confused exactly how youd want the mechanics from the skill trees you are asking for to work. All the examples you have given seem to be something that would require the game to be point and click to implement.
For the game to have your character decide to search for and find something based on stats it needs to take your agency away, and make the journey for you.
These things.. In an open world video game, are things you just make the decision to do your self.. No stats required.
So.. I guess its more of a question of what kind of game do you want.
An open world you can freely explore
Or something more like a choose your adventure point and click or something isometric that has a pop up to tell you your stat has activated and you find something on the ground.