I thought a neat way to make NPCs less dumb in games would be to let other players (internet connection required) to be the NPCs. They would have limited coverage area maybe set tasks and restrictions and let them fight a real person to move onto the next part of the game.
Basically set up a queue of player and what NPC character to play and when a user gets to that part of the game where NPC needs to load, you jump in and play. When the NPC dies you the game (scene) and get put back in the queue of playable NPCs.