How can I explain the difference between CS and coding to a layperson? I was at a party a few days ago with a doctor (the medical kind, not the research kind) who was thinking about writing a computer program to solve a scheduling problem at work. Someone introduced him to me because I have a CS degree and worked as a software engineer for a few years.

It wasn't long before we moved on from the specific problem he had (for which the answer was "hire a freelancer" or at least "I can't solve this for you just standing here with a beer and without a computer") to talking about computer science in general. To his credit, he asked good questions, picked up on the answers immediately, and asked smart follow-ups. But a lot of stuff that's second nature to us CS people was totally new and surprising to him.

The big one, which isn't surprising in hindsight but which we didn't get to until late in the conversation, was that computer science isn't the same as programming. There was also the fact that complexity/Big-O makes a real difference, and that the Halting Problem/unsolvability exists. It kinda made me feel like I wasn't a great ambassador for CS.

My actual question here is: how do you explain computer science to people when you have not a year or a semester, but just an hour, or even only five minutes?

(This question might be a little outside the typical scope for this site, but it's still relatively early in the beta, so I figured let's give it a shot.)
I regularly have to explain what computer science is to parents, and I have lately settled into this explanation:

Technology keeps changing all the time. You get used to the menus in Microsoft Word, and then they change it to the Ribbon. You learn to program buttons in Java using Applets, and then Applets get removed from every major browser as a security risk.

But there are some things that never change, because they're in the realms of mathematics, or they are fundamental organizing principles.  For instance, computer right now work in binary, 1s and 0s.  The properties of binary numbers themselves aren't going to change no matter what new technology comes around tomorrow.  We might create a computer that's not based on binary, but the properties of binary itself are fixed.  This is the realm of computer science.  Computer science is the foundational stuff that doesn't change.

It's highly mathematical, highly theoretical, and there are a lot of proofs involved, but when you study computer science, you are studying the deeper question in the nature of computation itself, and that's stuff that never gets dated.