SBaby
Dungeon Master
I think my biggest concern, if the games were to become more open directionally, would be with maintaining the steady difficulty incline. As we saw with the first few generations (particularly Johto, for some reason), when the game opened multiple routes for you to travel after accomplishment X, you eventually found yourself exploring a route where the challenges were calibrated to the team you had 15 levels earlier. Clearly, they can't have you beat the 3rd Gym Leader with your level 30 Pokémon and then give you the option of taking the path populated by level 45 Pokémon; but you also don't want to go spend six hours on one leg of your Pokémon game and then come back to your other choice and discover that you're suddenly a God in an environment of gnats...
So I'm all for increased exploratory freedom in Pokémon games, but only if it came with some mechanism of matching each stretch of your journey to the level your team reached at that point of the game. And then we also have to remember that the game must be amenable to childhood success, so they need to retain a high level of directionality and not-too-cryptic puzzles. To be honest, I'd say the argument that they've been doing it right enough so far is still pretty strong: kids have played every generation, and have been able to beat the games each time but also have themselves an enjoyable challenge doing it, and the sales figures are proof of the model.
There are a few solutions to the 'enemy strength' thing. If the game was going to be a completely open-world game, you could put a mechanic in it, similar to Skyrim where the enemies became stronger as you leveled up. Or you could go the Romancing SaGa route, where there would be thresholds, based on the number of battles you fought. This would require strategy and planning far ahead, as every battle, whether you run from it or not, would be counted. After hitting a certain number, the enemies would increase to the next level curve.
Personally, I don't think Pokemon has to be completely open-world like that though. It can still be linear, as far as the plot's concerned. But at the very least, you shoud be able to explore each area of the game in way more detail than you can now. Instead of following a straight path to your next destination, maybe the games could make the Routes more open, with field areas to explore, instead of always having a wall of trees blocking you. Kind of like how they do it in Ni No Kuni and Dragon Quest VIII. And they should make the individual Routes longer too. Make it feel like you really journeyed to get from one town to another, instead of traveling along one or two Routes and being there typically in a few minutes.