NSFU, AC is one of the longer games, Space Monkey, Sway, ROLE, Toki Tori, Dizzy Bee, Mecho Wars, Castle of Magic, Siberian Strike, MGST, Fast & Furious, MotoChaser, de Blob, Crash Kart, Bugdom 2, Snail Mail, Spore, Virtual Villagers 1/2, Armado, Ferrari GT, Bounce On, Rolando, Chop Sushi!, Midnight Bowling, Tiltafun, TV Show King, Cooking Mama, Wild West Guns, DJ Mix Tour. The only one on the list I might take off is MotoChaser if you don't like cats, because you're saving a cat. That helped me get through the game, which is great by the way.
I'm really liking Hi, how are you, as well. My favorite storyline so far is the one on Samurai: Way of the Warrior -- it's fairly simple, but it develops into a sort of classical tragedy. Bionic Surfer also has a decent story. 1112 seems to be headed in an interesting direction, but it's hard to tell with just one installment. There's Monkey Island, Myst, Return to Mysterious Island, and all the SCUMM ports, but those were all developed originally for other platforms and for that reason don't count as much in my book.
Myst has the best storyline but my personal favorite is Samurai. The story has (even though it's a storyboard) the right kind of feel.
Samurai and Assassin's Creed I agree. For my money, Samurai Way of the Warrior has a great plot. It uses game and manga to carve up a satisfying slice of the samurai genre. It's my favorite game. The only one that I continue to play almost everyday. I am hoping the devs turn it into a franchise with either sequels or added InApp storylines. Underworlds has a satisfying storyline, too. But I think Assassin's Creed deserves special mention. I was amazed at how long the game played. I kept expecting it to cut short here or there, but it kept going and developing. The plot is not as tight as say Samurai, but it is satisfying. I hope other devs follow the AC lead and make longer games for the iPhone. It's ready (and so am I).