Puzzles serve a few purposes:
1) They prevent players from completing the game right away. (Aka: Achieving whatever goal the game sets out.)
2) They are interesting in and of themselves.
If you find other features that perform the same basic functionality, then you can avoid puzzles.
For example: CRPGs use hoards of monsters to kill, to prevent players from completing the game right away.
By the way, I have lots of random thoughts about NPCs on
http://www.mxac.com.au/drt . I don't remember which articles specifically talk about NPCs, so you'll probably have to sort through a lot of them to find something that'll spur your imagination.
