I have an idea. It may be too hard to work with, though. So here it is.
The player character is a hero, but gets bored with his home country since he has smitten all the evil and has won the affection of all the ladies he ever wanted. He has a mixed reputation in his home country, but the player only gets snippets of it as the game goes on. So, he travels to a foreign country, where the game takes place. It could be some strange feudal-medieval Japan sort of society, except there is magic and giant robots and demons strewn about. However, these are rare and most of the populace are illiterate peasants. The hero, who does not speak the native language, lands in the country, comes to a village, and fights demons (a convenient place to put a tutorial). He seals them away, and tries to talk to some of the peasants. They are grateful, but a bit weary of the stranger, not having seen anything like him. Distraught, the hero goes to a pub, since all humans eventually find something to brew. There, a shady figure who was watching him approaches. It is a lord of some sort, and the leader of a rebellion against the current ruler.
Long story short, the hero has to fight royal guards, and can only speak to the lord, since he is the only one who speaks the hero's language. As the game progresses, perhaps the hero could learn the language and find out that
the current ruler is actually quite well beloved and brought piece. The lord you have been working for want to seize power, attack the neighbors, oppress random ethnic groups, and be a general dick to the people of the land(he just likes that sort of thing and/or wants things the traditional way). The hero could find out at some point, perhaps after he helps get the lord into power. He then will have to undo his mistake (or flee back to his home country).
There are my ideas. I hope they help.