I'll try to answer to the gist of each topic:
"Final Fantasy II":
Looks like the plot is relatively complex. It's a pity that it's a turn-based RPG and not an action adventure, otherwise, it might have been something for me.
Frozen in time, chocobo egg, pirates, Team Rocket:
That's the very thing: The egg is hatching as you're approaching it. You see stuff happen in the world.
With the pirates and Team Rocket: They are already there when you arrive. They don't spontaneously appear in the middle of a dialog of yours. Instead, you come to a new location and some NPCs tell you about the current situation which you then fix.
That's fine in certain cases. But those games never introduce stuff in the middle of other events, nor are there any events that only exist because of your own existence, nor do these situations redirect your goal and your path in any way. Each town has its problems and you solve them when you arrive. Then you continue normally.
In FFA that's different: The villain only attacks the town because you are in it and only after you had a talk with the local sage. The boy was only transformed into a bird to blackmail his sister to steal the pendant from you.
You wanted to take the girl to the sage, but the villain snapped her away, so your adventures take a whole new direction. You fell down an airship and ended up in a region that was never on your path to begin with.
"Ninja Gaiden" story:
No, I don't think the world is a literal two-dimensional plane. But yeah, the building where the cell is located is literally connected to the platforms that lead to the level boss.
And the path that leads to the level boss is literally platforms in the air. That's not necessary by gameplay, but was a conscious design decision: The platforms are drawn in a way so that they are held by large columns. There are many actual ground levels, but this one is literally some man-made construct high above the ground.
And the inside and outside are connected by a door, not by a level change, so yes, even if the overall way would be longer than the literal number of tiles, the connection is still literally there:
You leave some factory and end up high above the ground. Irene told you to escape, but you literally approach the boss. Which also means that Irene chose a hiding place within the vicinity of the boss.
The fact that you have to do mental gymnastics to make sense out of the story (he tried to escape the enemies and they "trapped" him and he "ended up" fighting the boss in the ruins by chance, even though nothing of this is seen in the gameplay) only confirms my statement that story and gameplay isn't well-connected.
Same with your explanations how Berzerker changed his clothes off-screen: They could just use the proper character in their cutscene. Or simply pretend that the guy from the storyline is actually one of the regular green ninja enemies and have one of them at the final door of the snow mountain level.
If you have to fill in the gaps of things that should otherwise be mundane plot details, then, by definition, the story isn't presented well.
And if they're bound by the gameplay, why didn't they design the story around it in the first place?
"We drove you 50 miles out of town and are now in the mountains. We took you here because we're close to one of Jaquio's henchmen. The exit of this factory leaves to his hideout. You need to go and kill him."
See? Perfect alignment of story and gameplay.
FFA ending scene:
Well, of course you should watch the whole plot. That link was only to contrast this ending with Gary's fate in "Pokémon".
Gary and fan speculation:
I was talking about the fact that the few lines Gary has in the game barely constitute as huge examples for a great story and massive character development unless you invent some fan fiction about his continuing depression and the way he deals with his loss in the coming months.
Please remember that I didn't ask you: "Can you list me random plot elements from random games?"
My intention was: Can you name me an 8-bit game that has a story at the level of FFA?
And that's what I get from you:
NO! That can't be! You beat my best! After all that work to become LEAGUE champ? My reign is over already? It's not fair!
Why? Why did I lose? I never made any mistakes raising my POKEMON... Darn it! You're the new POKEMON LEAGUE champion! Although I don't like to admit it.
That's it? That's your character development during gameplay? An acknowledgement from the final boss that the player is better than him? And you have to go to the next game to find 20 more lines of this character who by then is not even a main character anymore?
You wanna read some story scenes from FFA in contrast?
Girl: Hasim's got a serious wound!
Hasim: Oh.. please.. take this girl to.. Wendel.. and.. see Bogard...... He will take care of the rest.. ..
Girl: .. .. Hasim!? .. .. H A S I M!!
Hasim passed away.
Girl: Oh.. No.. Don't leave me alone, Hasim!
Duke: I'm looking for that Bogard, too. Why don't you come with me?
Girl: Oh .. Can I?
Duke: I can't leave you here alone. .. I am Duke.
Elena: Call me Elena.
(After fight with Medusa)
(The screen turns black)
Medusa: Came here to get my tears? Huh! What a joke!
(The screen slowly fades in)
Amanda: Can't find a drop of tear....
Duke: Let's go back to Jadd first.
(Duke walks away)
Amanda: ....Ouch!
Duke: Are you okay?
Amanda: I guess Medusa bit me while fighting.... .... One who was bitten by Medusa turns to Medusa. I'm gonna turn into a Medusa in a short while.... Please do away with me and take my tears, Duke.
Duke: No, I can't!
Amanda: I'm gonna be a monster.... I might lose my mind and hurt people.... Please.... Duke.... Before I lose my feelings.... Please take my tears to Lester. Tell him that I loved him.... .. Please .... Duke .... Pl.. please.. .. ..
(Amanda turns into a Medusa. Attack her)
Duke: ....I'm sorry, Amanda .... But I had to ....
(Examine Amanda)
(The screen turns black)
Duke took a drop of Tear from Amanda's face.
(Ish)
..See that, Auntie? A boy's falling!
Sarah: Oh, yes.
..A birdie is falling, too!
Sarah: Oh.. dear.. ..
(The screen fades then when it fades back in Duke is lying on a bed. There is another bed in the room and Bogard is asleep on it.)
Bogard: Duke....
Duke: .. Bogard! How've you been?
Bogard: I was thrown from the ship.... But Sarah picked me up and saved me. I'm glad to see you again, Duke.
(Duke walks over to the center of the room, and he has his back to Bogard.)
Duke: I can't do this anymore.. I can't do it!
(Duke turns and faces Bogard)
Duke: I'm not the right one to be the Gemma Knight.
Bogard: Come on! You must stand..
Duke: NO! What's that Gemma? .... Why me? Why does that have to be me?
Bogard: Duke, you..
Duke: You do it! You're the Gemma Knight. It's You!
Bogard: .. Shut up! .. SHUT UP!! ..GET OUT!! ..
(Town)
Sarah: He didn't wanna let you know, but.. He can't move for a while for his broken back. He was distressed to hear of places being attacked. But he kept saying that there is a boy.. A boy named Duke will come to save us all.. I didn't really believe him, but when I saw you.. .. Even a Chocobo knew you're the last hope.. Bogard and the bird made me believe in you.. We all believe that you'll save our world now.
For additional effect, couple the scenes with the following songs:
https://www.youtube.com/watch?v=1wKlnEb-ZEQ
https://www.youtube.com/watch?v=LGkQLzRuh08
https://www.youtube.com/watch?v=zKtMph0MkfM
Then you
might understand why "Oh no, I lost the Pokémon championship. Well, fair enough. Guess you're the winner now" or "Help. A single, unmoving pirate sprite has been standing in the same spot forever. Please defeat them in a duel and make them go away" cannot hold a candle to FFA's story.