You've hit the hard part, all right. And there is a distinct difference between shooting celebrities and cultural icons and shooting "real people". How many of Churchill's friends would have looked at Karsh's masterpiece and said (in today's vernacular), "that's so-o-o Winnie!!!" But it was very much the way the world needed to see Winston Churchill at the time, so if he only ever looked like that when someone had stolen his stogey or hidden his Scotch, it really didn't matter. He was an icon, and that portrait was an icon of the icon. In the same way, nobody wanted to know, really, what Archie Leach or Norma Jeane Baker looked like, they wanted pictures of Cary Grant and Marilyn Monroe.
When you're dealing with "real people", it's difficult to imagine ahead of time what that picture is going to look like. And it doesn't help at all that you are hampered by what sociologists call the Observer's Paradox — sticking a camera (or microphone, or even a notebook) in somebody's face and saying "don't mind me, just act normal," almost always has the opposite effect, at least in the short term. But you're not after the Daguerreotype look (a technically perfect picture lacking life altogether), nor is this a model shoot. You don't want people looking at the picture and saying, "that looks just like George," you want them saying, "that's so-o-o George!!!" The shot can be perfectly lit and executed, and can have a "great expression" and still be a failure as a portrait. You want an iconic representation of that person; someone their friends and family would have recognised from behind at a distance at night on a crowded sidewalk, to stretch a metaphor slightly.
That takes engagement on a personal level. Ideally, you'd want to have a bit of a pre-photo-session session with them, but that's not always possible. Let's assume, though, that you have something more to work with than the poor buggers who do school pictures (two a minute at least — "sit on the stool, 'assume the pose' and smile" is all the time you get for two exposures per kid). You can train yourself to be "intuitive", but it takes time and practice. (I started out life with something on the autism spectrum, and that led to some major problems that made staying that way untenable. People tend to mistake me for a sympathetic "people person" now, despite the fact that I'd rather be solitary almost all of the time.) Start with good body language and cold-reading techniques books. There's no need to make a study of it; just get the gist. If you can get them talking about themselves on any level, you can steer them deeper into their real lives, and they will become "real people". And you can get that transition from "client" to "person" down to just a few minutes with a little practice.
If you haven't had the chance yet, I'd suggest looking at Peter Hurley's videos as a sort of a rough guide. Most of the magic happens during the first "look" of his sessions, where the subject is minimally made up and simply dressed. (Later looks stretch people out of the everyday. These are, after all, actors' headshots and need to show who they can be as much as who they are. The first look is probably closest to who they are in everyday life.) You might not have half an hour at your disposal, but you can work in a bit of banter — and the disarmament tools are priceless.