A DIFFERENT KIND OF POKEMON

Removing the focus on powerlevelling to overcome obstacles and instead focusing on getting the right sets of pokemon with the right skills for handling many different scenarios makes perfect sense to me. There are a shitload of pokemon with all kinds of weaknesses and strengths, but they rarely matter in the original games. When they do matter, the strategy is to form a team that can handle any type of enemy, never to pick your team members based on what you're fighting. I can think of a few decent ways to do this:
1) Pokemon only have like 6-12 levels each before they max out. Each level awards a new skill, and the final level sometimes causes evolution. Levels have no other effect.
2) Make enemies level with you; either all of them, or maybe just the trainers (leaving wild pokemon alone).
3) Have the player able and expected to easily reach the max level with a full team of pokemon about 25% of the way through the game. Any new pokemon he brings into his team will need to be trained up to the max level before they're good for much of anything, but training his old ones any higher is impossible.

However, if you remove the ability for the player to have a single team capbale of handling anything, you will need some way for the player to know what pokemon to bring into battle. A way other than fighting each trainer once and dying just to see what pokemon they have. One option would be to show them on the field map before battle starts; another option would be to give the player a limited amount of ability to switch his backup pokemon mid-battle; another option would be to make them use 90% pokemon that can be naturally caught in the surrounding area so that the player can predict what he'll face if he paid attention.

Between the removal of a linear level progression and the addition of sidequests, it seems like you'd do well to make a much more nonlinear type game, even as far as the main plot is concerned. Your idea of making everything accessible from the start is probably good, although "everything" probably shouldn't literally be everything - unlocking stuff by doing other stuff feels good, and you want to have some more linear stuff at the beginning to guide the player.

If the gym leaders are all extremely powerful, for example, then the player could do them in any order. However, you do need less powerful "bosses" during the game besides regular enemy trainers so that the player feels like he's reached milestones. That's the purpose that the lower-powered gym leaders serve in the original games. They give you a feeling of great accomplishment every few hours for having made progress in the game. Moving them all to the end of the game kills that. Maybe you want to simply rewrite the purpose of gym leaders so that their placement in the middle of the game makes more sense? Or maybe you want all the mid-game bosses to all be related to other plot elements?

Edit:
Regarding walking sprites, check out the Pokemon Mystery Dungeon games. They have good walking sprites for a ton of pokemon. They're not battle sprites though. The biggest advantage of cutting to a seperate scene for battles in a 2D game is that it becomes acceptable for the enemies not to be animated. Do you really want to edit all those pokemon to create an animation for each of their attacks? (Actually three animations for each attack of each pokemon, since they can be facing different directions!) Of course, if you only have 75 pokemon, this becomes a little less daunting. But still really daunting. I'm making a game where battles occur on the field map Chrono Trigger style, and each enemy graphic takes me several hours to make. Even with only 75 pokemon, prepare to spend over a year just making sprites.

It's common fanon that a Gym Leader has different teams for challengers with different numbers of badges. Later titles have shops that scale with your gym badges as well, and so on.

Compare Roark's first team with his battleground team in Platinum, and you'll see what I mean. Of course Roark is holding back against a trainer with no badges - it's his job.

Taking this into account, you could make all of your leaders scale with badges, so they're challenging regardless of the order you challenge them in.

Also, for a comprehensive Pokemon database, use veekun.

holy shit that looks like something cthulhu would keep for a pet