Skies of Arcadia does well. You need to give it credit for having almost every cliché in the book, but managing to pull off a great plot.

Also, KOTOR has an excellent storyline. Sure, it may seem like a generic Star Wars movie at first glance. However, (SPOILER)there's so much you can uncover about the pasts of your allies, Jolee Bindo and HK-47 are both hilarious, and there's a shocking and original twist around three-quarters of the way through the game which you'll never see coming.