I don't really think they should make the levels higher when I think about it deeply, maybe just Lance's Pokemon cause the transition from RBY to GSC (in our case, FRLG to HGSS) in his Pokemons was ridicule.
I think they should just:
1. Raise the levels of some wild Pokemons
2. Make a better use of the Pokegear Phone function.
It was technically the first rematch function in a Pokemon game, aside of the E4 of course, yet it wasn't done well. Maybe if they'll make it occur more, and raise the levels each time, and overall do a better use with that thing, we'll have a success.
Only thing that should technically be modified is the level of the Gym leaders/E4.
And for all the "they had Kanto" people: Kanto, as much as I remember, had about the same levels as the Dragon gym leader. Maybe a bit higher, but they didn't pass the...50~ level limit more or less. And yes, it would be better if we had gym leaders with pokemons at 70s, or maybe even 80s instead of that. IMO, Red should have them all 90+ lol.
Oh, and Falkner just caught it in Yellow :3
Err, that's supposed to be a person. Caught it 3 years before GSC in Viridian Forest, and said to himself "Hmm, let's keep it to annoy newcomers in 3 years from now."