Flying is a weak gate because:
1) At level 1, a familiar can carry a grappling hook up the cliff/across the chasm, with a very long rope attached. This allows them to traverse gaps that are too far to throw a grappling hook. If the rope is long enough, the familiar might even loop it around something and come back with it.
2) At level 2, a druid can turn into a creature with a climb speed. This negates most cliffs as an issue. Now the DM can rule that a super sheer cliff can't be climbed, but it would have to be solid flat stone; if there are any grooves at all, a climbing animal will scamper right up there.
3) If the DM rules that an animal familiar can't set a grappling hook, not even if it succeeds on an ability check, then at level 3 a warlock can get an imp or quasit familiar that can certainly do it.
4) Also at level 3: levitate, spider climb, misty step.
So, really, by level 3 the party can probably navigate cliffs and chasms, and possibly earlier. There may be risks involved, like falling off the rope or getting attacked mid-climb, but those apply equally when the party has a flying PC.
This is just the reality of trying to run a "Metroidvania" style dungeon in an RPG. Given enough time and resources, the party can simply dig/cut/dissolve their way through most obstacles, if they really want to.
The secret is to not rely on gates, but enticements. If the party has to choose between climbing a treacherous cliff or simply walking down a hall, give them reason to suspect that their quest goal is down the hall.