I'd start with Platinum. It's the oldest Pokemon game that still retains the most unchanged battle system. It's also the best. Great, epic story. Good world building. Good Pokemon. Fun and interesting characters. A ton of content throughout the region both during and post game. Most interesting region geographically by far, second only to HGSS Johto.

Platinum will make you fall in love with Pokemon. No better place to start.

I would advise against XY though. It lacks all the charm of the older games and the story is terrible and the characters are terrible. I feels like you're playing an episode of Barney, which is not the impression anyone playing Pokemon for the first time should get about the entire series.

You don't have to contextualize every little thing that you do. However, the events that separate the games from each other in terms of story tend to be small things like these. If there's not much going on in them, then there's not much separating their stories. (In the games I played. I noticed that almost everything you mentioned comes from the games I haven't played.)

The evil teams however seem pretty shallow.
The details you're quoting about the 4 admins leading Team Rocket only appears to be from HeartGold and SoulSilver. In Crystal, it was very different.
Here's an explanation:

"Proton's position has existed since Pokémon Gold and Silver. However, his existence was easy to miss because all male Rocket Executives used the same sprite (now adopted as Archer's canonical design) and were not identified by name, making it seem to some like there was only one male Executive. The Rocket Executive (as well as the grunt) Proton is based on was then given a canonical design and an official name in HeartGold and SoulSilver, along with the other three Executives, to distinguish them as individuals."

So the story you're talking about, from a Crystal players perspective, is about characters without individual names, sprites or story.
In HGSS it sounds a lot more developed than what it was in Crystal. Same for the Kimono girls, Clair, and probably Ho-Oh and Lugia as well.

Keep in mind that I've only played Yellow, Crystal, Emerald, Platinum (80%) and X.
And they're all basically the same story for me, with X being a slight exception. Which I'll get to in a bit.

Regarding what I remember or not, well it's an observation I've made about the games and myself.
I've played many many rpgs over the years. But how little I remember or take away from the Pokemon games really stands out to me, and I have to ask myself why.
Not sure what you mean by "depth of it's plot behind the scenes", but if it's things like getting pieces of the story from NPC's, side quests or reading from an in-game database, I generally have no problems with that, as long as it's interesting and feels worthwhile. But if there's not enough story on the surface to begin with, then I'm not expecting there to be much behind the scenes either.

I talk to every NPC I see though, multiple times just to see if they have something else to say. What I usually do avoid in Pokemon games however, is reading the books on the bookshelves. It usually seems to be about something like the everyday use of pokemon in todays world, or lore about some pokemon.
In X I believe I found some books about the King who wandered for 3000 years. And those I did read. Because they presented that story in an interesting way before I even found the books.
I'm not as interested in reading the lore of pokemon, because of the way they represent themselves in the games.
For example, in Xenosaga 1, there's a character who seems pretty interesting and mysterious. And only after reading about him in the database do you find out that he has lived for hundreds of years, dating back to an event you see at the beginning of the game, where he apparently was involved. It's odd to keep this information secluded to the database alone, but it was an interesting read and felt worthwhile, as that character is present in all three games.
A pokemon however does not have such a large role in the story. So reading about the origin of some pokemon in an optional manner I see more as a side story rather than an important addition to the story at hand.

Regarding what I remember from the games though, if you show me a pokemon town, chances are great that I couldn't even tell you which game it is from. If you show me a (human) character, I most definitely will not remember their name. I can tell you the only names I remember are:

Yellow: Oak, Garry*, Jesse*, James*, Misty*, Brock* Giovanni, Lance. (*Only because of the anime.)
Crystal: No one.
Emerald: No one.
Platinum: Cynthia.
X: AZ

This is unusual for me, as among all the rpgs I've played, I don't think there are any that I've played within the same timeframe where I couldn't tell you the name of a single character. Or only one.
I remember the guy who joined me to fight off enemies in a cave in Platinum. I remember him because he had a Lucario and gave me a Lucario egg. I definitely don't remember his name, story, what he looks like, or anything he said though. And that's the case for most of the characters I run into in the games. And most of them aren't even as interesting as him, since they don't give me a free Lucario. Well, one guy did in X actually. But once again I can't remember this character's story, what he looks like, or his name.
But I remember the name, face and story of every character in Metal Gear Solid 4, which I finished right before I finished Pokemon X. Actually, I even remember the name, face and story of every character in MGS 1, which I last played many years ago.
Why is it so different for me with Pokemon games? It's not that my memory sucks. It's that my brain doesn't think it's worth storing in my memory.

I think it's partially because each game feels like a retelling of the same journey, with shallow alterations, and small additions.
Most of the games you mention having a good story are the ones I haven't played though, with the exception of Platinum. I got as far as the 7th gym in the snowy mountains, and it does not sound like we played the same game, because that to me was the same game as Pokemon Yellow, Crystal, Emerald, and X so far. Meaning a rather simple and shallow story. And pretty much the same as in the other games.

I said before that there were some exceptions in Pokemon X though.
Mainly it was AZ's story. I think they really presented it in a nice way that was memorable. Like the sad music that played while we saw images of the events from 3000 years ago. And it felt like an unusual story that stood out as it mentioned people (pokemon) dying. I don't think death is a common theme in the world of Pokemon. The prospect of death is there, but I don't recall anyone actually dying.
But more than that, it made me care about the character, and his pokemon. And it was really nice to see them reunited in the end.
And this part of the story is already more memorable and interesting for me than the main plot was.

Another part was when the main character and his friend (not the rival) were standing on the balcony looking out over a garden to watch fireworks.
Nice music was playing, and we got so see some some nice character development from her while they had a heart to heart. Sadly, this didn't lead anywhere though. I was hoping for another scene like that, but it never came.



But after seeing these things, it made me wonder why they don't add more of these things in Pokemon games, and if Pokemon games could have an actual story worth caring about.
See, even if the villain's grand scheme seems larger and more significant (something about wiping out all humans and pokemon), it's all rather shallow unless it's backed up by a meaningful and coherent story. And it wasn't. I can't relate to it (world being overpopulated) just because he says it is. Did we ever see this being an issue anywhere? Towns where people were starving or killing each other over greed? No. I could draw parellels to our world, but I'd rather not.
But a simple thing like your friend having a heartfelt conversation with you really stood out to me. Partially because I've never seen anything like that in any other pokemon game.

That said, the overall story of Pokemon X was still as weak as in any of the other Pokemon games I played. But with more events like that, and it could turn into a memorable story.