I never had a problem with where you obtain "Fly" in Red/Blue. It made sense to obtain it there. Especially since you couldn't even use it until around that time anyway. You know, the Badge Requirement.
Your route is linear up until the point you obtain it, and you only obtain it once the game opens up and says, "okay, now you can pick your own way forward from here".
The Route to the Rock Tunnel is "one way", so giving you fly before this point invalidates the point of having the "One Way" path. Once you are halfway down that Route and hit the "point of no return" your only way back out of it is Dig, Teleport, or lose and be sent back to the town.
Even then, you've got some genius design. At the end of the Route, just before the Rock Tunnel... there's a Pokemon Center. If you heal your Pokemon here... Dig and Teleport and Death now transport you HERE instead of the latest town. You're 100% committed to having to go through the tunnel now.
This is a "soft trial" for what the Elite Four is going to be like. Complete with "Challenge from Rival" at the end of the long and grueling trek while your Pokemon are insanely weak.
It's pretty Genius Design.
If I recall, you need the third Gym Badge to even utilize Fly, but you can obtain the HM after the fifth gym. To get to the 5th Gym, you need to at least visit the Celedon Department Store and buy a drink for the guards so they'll let you into the city. Once in the city, I think you're locked away from the Gym by Team Rocket, so you have to defeat them at Sylph Co. You obtain the Sylph Scope there and the Master Ball. Then, you can leave and go finish the Lavender Town Pokemon Tower... or complete the Fifth Gym. I always do the Gym so I don't really have to come back. The trek back to Lavender Town is very short. Complete the Tower, catch the mons I need, and then obtain the PokeFlute and the Bike. The Flute can be used on Cycling Road or south of Lavender Town in order to progress to Fushia City. Since I just got the Bike, the game is telling me to go to "Cycling Road", since I knew about that route pretty early on with everyone talking about it in and around Celadon. Catch the Snorlax, gives me access to the route and the HM for Fly.
It's worth Noting that you can't use Fly until you've got the third badge, but you can't obtain the move until after you've at least passed through the city containing the fifth badge. So, you can "sequence break" a traded Pokemon in with Fly in order to use it early if you want.
But, here's the problem:
I haven't needed Fly yet. There's no reason to need it. The Routes between the 3 Cities I just utilized are so short, that it's not really necessary to have it. I'll use it now only to clean up Routes I haven't traveled down. Even then, I'll most likely need Strength and Surf to complete that prospect. The Route south from Lavender Town hasn't been explored yet. I'll probably also need to come back to Fushia City at some point for the Safari Zone. I'll also have to fly out to Cerulean City so that I can move passed the Rock Tunnel to collect Zapdos.
So, I could go west from Fushia City after obtaining Strength and Surf and the badge to use Strength (6th badge) and that goes north to Lavender Town. At which point, I'd need to use Fly to get to anywhere still "useful". Or, I could go south to Seafoam Islands and catch Articuno (it has Uno in it's name, so you can guess which direction the game basically wants you to go first and expects you to go first).
Hit the Seafoam Islands, then move on to Cinnabar Island for Badge 7.
Then, head north from there back to Pallet Town and Viridian City. You might have forgot at this point that Viridian City had a Gym (I did on my first run!). But, people tell you that the Gym is open now. Good thing Viridian City is where you have to go to even begin the route toward Victory Road. So, you have to come back here regardless, due to the map design.
Beat the 8th Gym and Victory Road is open.
At this point, you've probably seen a few items you've missed on these previous routes because you didn't have access to Surf and Strength (so, you got a handy little reminder, if you've forgotten!). You can now obtain these items. Seeing that you can get them will basically remind you that there's a lot of other stuff you passed up along the way here. So, you hit up every town you've previously visited using Fly to finish up that exploration.
You'll remember or find Zapdos at this point. And this is where Fly is going to get a ton of usage from most players.
Some players will remember these locations the moment they get Surf/Strength and begin their "revisit tour" after Gym 6. Good thing they got Fly before heading here. Few players remember that Lavender Town has a south exit and will inevitably head back to Celedon City to tackle Cycling Road because... what the heck is Cycling Road? You've got a bike and it's fast and awesome! Cycling Road it is! So, good thing Fly is right before Cycling Road. I mean, you just RECENTLY got your bike, didn't you? The game is obviously telling you to go to Cycling Road after you get your bike. You know, the bike you can only obtain after saving Mr. Fuji from the top of the Pokemon Tower in Lavender Town. To top it off
So, here we are. Not even needing Fly until after obtaining Badge 6, and probably not utilizing it until after Badge 8 to clean up the rest of the game before going down the last roads of the game to the end.
Then, once you've beaten the game, you'll only use Fly to go to the Safari Zone or back to The Elite Four for capturing/leveling purposes only.
Pokemon Red/Blue gives you Fly long before you ever need it and would ever use it.
The only "backtracking" the game requires of you happens AFTER you've beaten the game. It's all optional up to that point, and it's really only in service of exploration.
But, you will have to Fly back to Cerulean City once you've beaten the Elite Four. At least if you want Mewtwo and the last dungeon in the game.
You don't get Fly until you absolutely need it, and won't use it until a while after you've had it, and it doesn't become "necessary" except in quickly obtaining two Pokemon (Zapdos and Mewtwo). But, if you got a friend willing to trade you a mon with Fly on it... you can use Fly as early as beating the third Gym. Not that you need it this early.
Even going through Diglett's Cave is only useful to catch Diglett, get your Farfetch'd, and obtaining a couple items. Backtracking back through Diglett's Cave and then to Cerulean City isn't that big of a deal at that point. It's a very short jaunt. You probably also need the levels at that point to tackle the route to Rock Tunnel as well as Rock Tunnel and your Rival battle immediately after it.
Red/Blue doesn't have any "backtracking" in the game that really needs to be done until very late game, long after you've obtained Fly. It's given to you at the perfect place for it. You don't need it at all until that point.
I think Gold/Silver does something similar with Fly. Gives it to you only when you actually need it, otherwise it's basically a straight line through the whole game.
Ruby/Sapphire/Emerald, on the other hand... Lord do they not give you Fly soon enough. That game is like 90% backtracking and forcing you to do it on foot... Especially when so many routes require you to have different versions of the bike to even traverse... which means you need to get back to town to swap that bike out, and you won't have Fly to do this for quite some time, so "cleaning" these routes is a massive pain in the butt and highly dependent on which bike you're using at the time.
It also doesn't help that the map is so freakin' massive either.
It's a little better in Pearl and Diamond, but not much. That map is massive as well with a ton of backtracking too, and not giving you Fly for a while.
I think X and Y is the worst in terms of giving you Fly and requiring a ton of backtracking, if I recall (and I am probably wrong). I remember a lot of "go here, come back, go here, come back" from that game and wishing I could just skip that or have Fly to make it faster.
Anyway... You get Fly at the perfect place in Red/Blue. You are given it long before you ever need it and even further before you'll ever really utilize it.