I'd suggest Gamebook Adventures 1: An Assassin in Orlandes. If you haven't played a gamebook before its like a choose your own adventure book, where you make decisions on what your character will do next. Its certainly not an action oriented game, but if you want a story this is what this game is all about. There is a good amount of replay based on following different paths to discover more information that fleshes things out.
I actually have this game. One of the greater stories in the app store. Not to mention best controls I've seen on the device.
If you want to check out some of the best-written video games of all time get Frotz and put a bunch of classic Infocom games on. Not everyone can get into text adventure games, but you might be surprised, there is a lot of richness there. You can have the PDF manuals and other materials in Goodreader or similar for reference and to add to the experience.
The witcher on PC is for me the game with the best written game I ever played and from far. I'm curently playing Dracula The Path of the Dragon HD, that's a good story with a good writting quality. Very good game.
Across age (has been mentioned already) Rayman 2 (it's a port of the original PC Rayman 2, and the story is awesome. It can get quite frustrating at some points, mainly because you can't save during one level, so you have to either complete the level or you lose your progress on that level)
