Dag nabbit...
How can I make it harder...?

I cannot put the king and say his favorite line is MAI BOI.

Heres an idea, don't say the game they're from or their gender. Also, a better thing to try is something along the lines of:

This character often says "huh" at the end of his sentances

or:

This character wears a glass eyepatch and is the captain of his own ship

rather than the little factsheet you gave us. This method gives us one or two unique details on the character. Another strategy you could use is to use slightly less popular characters in popular or less popular games like Vyse from Skies of Arcadia, Mike Jones from StarTropics, or Suzu from Tales of Phantasia. Just don't make it too hard or people would find this game boring, throw in an easy one every now and then.