The starters most definitely do not have to be simple. The fully evolved forms for starters, over the years, have run the entire gamut of stat distributions and ease of use, and it's been this way ever since picking Charmander would put you at a disadvantage against the first two Gym Leaders in Kanto. (For that matter, I'd say picking Chikorita in Johto would give you a pretty hard time too, not only because you'd have to find some other Pokémon to deal with Falkner, but because Meganium's wall-like stats make it inherently more perplexing than the more straightforward Typhlosion or Feraligatr.) After all, by the time you get their final forms, you should be far enough in the game to have gotten the hang of battling and can handle less beginner-friendly stat and move schemes.
Rather, the learning curve is usually built into what other Pokémon you can catch will be. You begin with Normal-types, Flying-types, and Bug-types, which are easy to identify, and the early-game Pokémon have mostly attack moves with a few simple status moves like Tail Whip, Growl, and String Shot. And these Pokémon will be the same no matter which starter you pick. Later on, they introduce you to other types, like Grass (if you didn't pick a Grass starter), Rock, Fighting, and Poison with status conditions, and the first Gym Leader will almost always use a type that resists one of the early-game types but is weak to some other types you can get to teach weaknesses and resistances. Only later on do you get steady access to types like Ghost, Steel, Ice, and Fairy (not counting Pokémon retconned to be Fairy-type, like Jigglypuff and Ralts), which are advanced and whose vulnerabilities are not obvious. When your starter fully evolves, you'll likely be at that point in the game.
Even then, though, the NPCs stick to pretty simple strategies and will rarely throw Pokémon at you that you haven't encountered or at least guess at how to fight it. That's why Shedinja only comes up in the post-game or sidequests. They know players might not necessarily have something able to fight it, and even if they do, they won't necessarily know what Wonder Guard does.