When I think of that,it kinda makes me think of Lance's Dragonite, so give them different evolutions and amount of pokemon based on the level the trainer's at. Like Surge would have 5 pokemon that are FE or 2nd stage instead of 2-3(I forgot how many he has) if you faced him as your 8th gym leader.
Also, what about wild pokemon? Should those be scaled too? If you chose to start in Fuchsia City, it would be awkward to have all the Safari Zone pokemon being levels 4-8 forever wouldn't it?
Also making the gyms not-so-monotyped, like not gabbing the nearest fighting type for a normal gym and whatnot.
"...and left into the vast world that had way too many Fire, Ice, Ghost, Steel, Dragon, Rock, Flying, Poison, and other Bug pokemon."
Check out my super Bugrasslocke!