Some natural walls, like the Upper Himalayas, are impassable to all land units even today. Others are impassable for a large part of the year. On the other hand mountain ranges quite commonly have passes, which can be very strategically important. The terrain generator isn't very realistic, mountainous areas usually have a number of valleys with a river or stream running in the middle of them. Sometimes the valleys are interlaced from either side like cog wheels, sometimes they are connected through passes, sometimes the valleys run through the entire range. Maps, or really local knowledge, could help an army get through.
It might be useful to discern between adverse and hostile terrain. All terrain is to some extent adverse, though it is much harder to cross a mountain or a swamp than farmlands. Not only is the going tougher (and too tough for some), bringing supplies or foraging can be near impossible. The attrition (hit points) aoproach can model this nicely. You can easily cross a lava lake, but you are dependent on getting supplies on the other side. If you have to fight another army on the other end instead. then you are in a poor position.
Civ already has sea and jungle as hostile terrain. This is terrain that regularly kill you. Adverse weather, poisonous fumes, disease, avalanches, the ground swallows you up, animals will eat you. There is plenty of this kind of terrain on Earth, the terrain in fantasy and science fiction is even more brutal. The terrain doesn't have to be deadly to be hostile, eternal fog might disperse armies, bathing nymphs might distract them.