Quoted By:
Maybe it's uncreative but I'd do a 3d, cell-shaded MMO.
Imagine cell-shaded WoW, but you control your trainer outside of battle and your Pokemon in battle. You have a team of 4, each with 6 abilities that they learn whilst levelling up and you can chose from maybe a sample of 12 for each Pokemon.
Combat is similar to a 3rd person MOBA game in a small arena, with skillshots etc. You can start in Kanto or Johto and move through the next zones doing all the Gyms/Leagues to go to the next area.
Pokemon simply walk around, run around, swim around, fly around in open-world areas, and you walk up to them to initiate/fight/catch whatever.
Rare Pokemon like the Beasts will literally run around the world until someone finds them and catches them.
Pokemon like the legendary Birds and all the cover legendaries have "Dungeons" or "Raids" where a group of 5 go in, fight wild Pokemon and eventually fight the boss. The Pokemon go in alone so no trainer for catching. They just have a very low chance to drop an egg which has a very low chance to hatch into something good.