If you want an RPG example of making a game non-liniear (shameless self-advertisement) try Words:
http://www.rpgrevolution.com/forums/index....showtopic=51319It's got the NPC personality thing you mentioned and sidequests that change the plot as you also mentioned.
The best way to get ideas for your game is to see how other games use your ideas and how you can morph them into innovative material.