Twice Your Protector, - simple as. In the series of FF, the answer has been your protector twice. However, MsTiffie says that you may not have been directly protected. So it may not necessarily be a *swoop saved your life swoop* kinda deal.
Three Times A Foe, - simple as again. This could mean that you fight the answer three times throughout the series, or it could just be that the answer doesn't like you much. Tiffie says these lines are a bit tricky though, so I imagine you actually meet the answer more than these five times?
Each Time Met Royalty, - Face to face. Not Garnet. My knowledge of other games pretty much screws me for this part, as I haven't played enough. Or at least can't remember enough. All I remember from other games is Sarahs, but Tiffie says it's not Garnet. I just reread some of your hints. This line is literal to the first two lines. This could mean that the character met royalty in the protector/foe events, or it could mean that the answer met royalty. Hell, it could also mean that the protector/foe is the royalty.
And Would Not Let You Go, - In reference to the circumstances in which you meet the answer regarding the five times we know we meet it. This further suggests that the answer is actually met more than 5 times, in my mind. But maybe not. Anyway, this suggests that you are forced to meet the answer. For example, a necessary boss battle, or a necessary meeting to continue the story etc.

You May Misunderstand Me,
My Guardians Say The Same,
But If You Research Me,
You'll See In My Fame

This confuses me, I'll be honest. We may misunderstand the answer in a Garland way. Garland is technically a bad guy, but he's trying to restore his homeland and his people. So the foe times may just be because the answer isn't evil, just misguided. And the protector times may happen when we think the answer is a bastard. Maybe, I dunno. The Guardians say the same in that they misunderstand the answer also? Or the guardians may literally say the same in that they are senseless drones.

"If you research me, you'll see in my fame" has me stumped. My knowledge of fame is that it refers to the reputation or generally opinion held by many, so that's what I'll apply here. So...we'll understand why the person is misunderstood if we researched them more thoroughly? There's more to them that meets the eye, perhaps?

I haven't an answer yet, I'm afraid. Just throwing some ideas out.