I realized recently that one problem with these types of talks is that (in the US at least) the audience often has no idea where mathematics comes from, even in a naive sense. In psychology, physics, engineering, etc, most people have a vague sense of what the roots of the discipline are. But in mathematics, particularly pure mathematics, the sense of purpose of mathematics is what is usually missing from a lay audience member.
I have found the work of Saunders Mac Lane in Mathematics: Form and Function to be very helpful when discussing mathematics with non-mathematicians. Once these ideas are "in the air," then the specific problems like Euler characteristic, graph coloring, etc, have a context in which to be appreciated (I agree that trying to discuss specific research problems at the lay level is typically impossible in pure mathematics). Mac Lane's argument is very roughly the following:
- Human cultural activities lead to
- Recognition of mathematical ideas, which lead to
- Mathematical formalism.
There is a nice table on the wikipedia page about Mac Lane's book with lots of examples of this. If I am giving a talk about what mathematicians do, or what mathematics is about, I discuss Mac Lane's ideas first to set the stage for what is to come. It is remarkably easy to discuss this in just a few minutes, and might be helpful for your situation as well.