Here are some examples of narrative that are interesting in some way. My initial thought are to keep the graphics and game-play fairly simple and to make a more complex narrative and story.
In "The Stanley Parable" the narrative is very interesting, where your actions are recorded by a unnamed narrator. Eventually you get the chose to contradict his predictions and change the whole story. You quickly get confused and never really know whats going on or who to trust.
http://www.stanleyparable.com/
Memento is a well used example of a nonlinear narrative,where the story is not reviled in chronological order.
http://www.imdb.com/title/tt0209144/
Similar to "The Stanley Parable" the character progresses through the story as it is narrated by some unknown entity.
http://www.mikebithellgames.com/thomaswasalone/
Here are some examples of gameplay styles that are interesting or relevant to the project. I am thinking of including some puzzles or challenges but keeping them simple and easy to complete.
"5 Days A Stranger" was one of the first point and click style games I played. I enjoyed it greatly and got sucked into the story, however I was unable to solve many of the puzzles which was very frustrating.
http://www.fullyramblomatic.com/5days/
Here is an example of a modern point and click game that has been very successful. The puzzles could be just as difficult but better user design helps make them easier to solve.
http://www.thelastdoor.com/
In "Journey" the narrative is very linear and the gameplay is simple, but the experience is a very engaging story. The puzzles are enough to make you think but not to hard to slow down the game.
http://thatgamecompany.com/games/journey/
In "Dear Esther" the player fines them self awake on an unknown island. Exploring the island progresses the story, however unlike a conventional game there are no puzzles or challenges to halt the players progression.
http://dear-esther.com/
"Device6" is an interesting mix of image and text. A normal book becomes a interactive journey.