Player characters often have extreme freedom of action in the campaigns that I run; as a result, I often have to create non-player characters on the fly, in large numbers. Nonetheless, one of the things that I'm noted for as a GM are my NPCs. My secret? I cheat. :-)
I've found two great sources of inspiration for NPCs: the real world, and the media. By patterning characters on people that I've known or seen on TV, I can quickly and easily create a clear and self-consistant personality that makes a strong impression on players. The surprising thing is that I've almost never been caught. And even when I am, the player is never quite sure -- and often seems strangely impressed.
The key, I think, is to be careful about who you imitate. Choose memorable minor characters in preference to major ones that might be recognized. Change one or two major elements, such as gender or age. Make the character your own by giving it a unique quality; a tendency to whisper, perhaps, or a habit of nodding at the end of each sentence.