Thought I'd add to this regardless.
What makes an NPC memorable? For me it's the voice acting.
Characters like Leonardo Da Vinci and Torquemada from Lionheart: Legacy of the Crusader; Morrigan, Alister and Sten from Dragon Age; Bastila, Malak and HK-47 from KotoR 1 and Kreia and Atton (HK-47 again too) from KotoR 2 all had great voices which suited the character perfectly without being cliched.
On the other hand Wynne and Oghren (Steve Blum is a great voice actor, but typecast so much), Carth and Canderous, Disciple, Handmaiden and Visas were all weaker characters (to me) because they were too generic for my tastes.
However I think that actually it's a pretty unusual line to take and more often than not it's the writing that carries whether a character is a success.
I'm going to prefix the next couple of lines by saying that for non-fiction I prefer films to books. For the writers of a book or game with no voice acting its more difficult to appeal to the portion of the audience I'm representing so the writing has to really carry it and give accents and nuances to the characters. In a book its much easier with a (terrible) line such as 'In her thick Glaswegian accent', which is sort of immersion breaking at the time because when talking to people the first thing you think about them isn't usually their accent but in the long run benefits the story by not having to keep a Glaswegian to English dictionary beside you while reading.
However in a game it's not usually possible to add exposition as background is told via imagery. In which case it's the dialogue that needs to convey accent, relative intelligence level both to other creatures and to others of its own species, state of mind and nuance to indicate things like possible deceptiveness or loss of free will.