Whichever idea you choose, it will always sound like a cliche if it's summed up in 2-3 sentences, so I wouldn't worry about that. Look at Final Fantasy V plot summary for example: there are these 4 warriors that find 4 crystals with powers of the 4 elements. You can't be more cliche than that, yet the story was considered really deep and engaging.
I would gladly help you some more, but I know too little about the game - "TPS" isn't exactly the description of mechanics and these need to be taken into consideration when writing a story. Think twice what narrative means you want to use for this game and how story-heavy you want it to be when you are having doubts when putting together a very, very general plot.
Remember, that even the worst movie can be sometimes saved by a good actor. Even most cliche story can be saved by a well-thought of character. If you are having a problem developing a main hero, treat it like an RPG - decide on the gender/class/skills/attributes and all that stuff. Do all you can not to make the character OP, give it some faults (just don't make it a bearded alcoholic - Raynor and Payne pretty much stole the show here), also try to give a chance for the player to identify with at least some of your hero's characteristics. For example, f you make it 100% cold-blooded bastard people might find it too abstract.