I have used several examples on non-mathematicians that seem to have an impact.
The stable marriage problem. Here you can do no better than use Gale & Shapley exquisite presentation. If you have not read the paper, maybe you ought to. It is very rewarding.
Six degrees of separation problem. Each person is at at most 6 n hand shakes away from the President of US. (There is a version where Kevin Bacon takes the place of president, though experimental results show that the average number of handshakes away from Rod Steiger is 2.87) What does this have to do with mathematics? The paper Random graphs models of social networks by Newman, Watts and Strogatz may explain why. The stories in the first part of this paper can be used as a conversation starter with a non-mathematician, but mathematically curious person. The book of Durrett Random Graph Dynamics studies this and other problem in greater mathematical detail.The story is juicy. Open these references for inspiration.
Teorema Egregium, the one that says that the Gaussian curvature of a surface in $\mathbb{R}^3$, which is an intrinsic quantity can be expressed in terms of the second fundamental form, which is an extrinsic quantity. The way I tell the story to non-mathematicians is with the help of a handkerchief. It can be wrapped neatly around a cylinder (no folds are formed), by try wrapping it around your head so no folds are formed.
Then, take a piece of a very elastic material (say a piece of a surgery glove. You can wrap it around a cylinder, you can stretch it over a spherical shape such as the top of the human head. You can do this without forming folds in the elastic surface. Then as the audience what is the difference between a cylinder and a sphere, why can the handkerchief (which is flexible but inelastic) can sense the difference, while the elastic material cannot.
Sneak in there the word curvature, tell the story of Gauss who discovered that our Universe is curved, tell of Eddington sharper experiment on the curvature of the Universe, and end up giving Einstein's explanation as curvature as gravity that bends the straight lines that are supposed to be the trajectories of photons. usually when I tell this story, people stop asking about the uses of mathematics. They get why it is fascinating.
The Radon transform. I told this story to my dentist. He installed a 3D printer in his cabinet. He took many shots of a tooth that was missing a part. These were automatically fed into a computer and, I kid you not, the computer 3D-printed the missing part, matching size, shape, color, all in the span of less than one our.
I was so impressed about this that I told him about the Radon transform that happened to capture my imagination at that time. I told him that I never thought the technology had advanced so much that it could simulate the Radon inversion formula. I left him as impressed about the power of mathematics as I was about the advances in technology.