Honestly, going back and replaying Gens 1 and 2, even then the gyms were only slightly harder than they are now, Back then, it had more to do with actually using good Pokemon than just leveling up the ones you found on the first Route.
Like for example, In Gen 6, you can go through pretty much the whole game with Pokemon you found on the first three or four routes, just outside the first town, the forest, and Santalune city. That's more because the Pokemon are just better overall, and maybe because the gym typings are changed.
It used to be the first gym was rock like in gens, 1, 3, and 4 (? Didn't play generation four all that much.). Which meant you didn't have a team that could hit the Pokemon effectively, if you picked the fire starter. There were always Pokemon you could catch to hurt them, yes, like Mankey/Nidoran in Gen 1/ their remakes (Nidoran learns Double Kick).
If anything, yes, the games have gotten a little easier over the years, but that's more because of power creep and how they placed the gyms in my opinion. Like in Gen 6, the 2nd gym is rock, but you find type advantages against it rather quickly. (Pancham, Machop, Onix, Cubone, and Skiddo off the top of my head, not to mention the two Kanto starters that have an advantage).Whereas, if the Rock gym was first, you would have to rely on Pansage, if you picked Fennekin and NOBODY wants to rely on Pansage.
If you had to change your Pokemon out more often as well, then the game would be more challenging. Like in gen 2, you really couldn't beat the game with what you could catch early on. Same with 1, unless you over leveled them.
That and all you had to do was go to the Diglett cave and catch a Diglett or Dugtrio, teach it Dig, and laugh as Lt. Surge cries.
Also, you could get a Machop from a dude in the Goldenrod Department Store for a Drowzee that you could catch just outside the town, makes making Whitney cry even more sweet.