Not Everyone Is Fred
Even for those who prefer to develop roleplaying stories on the fly, this handy tip is quick to set up, is useful in any session, and can save time at the table: Come up with a handful of names (and maybe vague character descriptions) before starting a game. Don't assign them to anyone; just have them handy.
If you have a list at the ready, then when the players go somewhere unexpected or undefined – a tavern, a specialty shop, a minor noble's hunting estate – you have a menu you can pick from: "Ah-HAH! That sounds like a good barkeep name." It'll help avoid duplication and homogeny, giving a nice variety while also speeding up gameplay.
If you want to be clever, you can divide them according to how each one would be useful: "Older character names," "Elven names," "Stage names," and so on. But, honestly, I've found just having any such list makes more improv-style games a lot smoother.
-- Steven Marsh