Interesting. I wonder how technical you could get by taking a Socratic sort of approach. Perhaps you could get people to understand basic first-order logic, or at least that logic can be codified. When I start off by trying to define first-principles like implication and Boolean algebra, eyes start glazing over. But in my head, the conversation could be steered by acting like a human REPL while talking about a hypothetical first-person shooter or something:

"When does the player die?"

"When their health is 0."

"When do you decrease their health?"

"When they get hit by bullets."

"So, you tell the computer: if the player gets hit by a bullet, then you should decrease the health. If the health is 0, then the player's dead. How much damage should they receive from a bullet? What if it hits their head?"

etc., descending into further complexity until they get the idea of how much they take algorithmic thinking for granted (which I think is probably the most essential thing to realize about programming).

Of course, actual conversations consist of me yakking about over-the-top technical details, amounting to the usual response: "Magic. Got it."