I think the graph isomorphism problem is a good choice: it's a fundamental question and a good lead in to the notion of isomorphic and some complexity theory---it's not known if it's NP-complete. This should be doable in a couple of lectures, depending on how thorough you want to be.

There are also applications, but I'm not the one to tell you about them.