I would suggest having a look at the opaque square problem. The story of the problem is the following:

Suppose you own a square piece ofland and you are being told that a phone line runs through it. As you have no phone and internet connection yourself, because the phone company cannot, or will not, provide it, you want to find this line and rig up the thing yourself. Now the question is: how long is the shortest trench you would have to dig to find this phone line?

If you restrict yourself to a connected trench the optimal solution is a Steiner tree for the four corner points. For a trench system consisting of two connected parts, there is also a shortest solution known, which is shorter than the one consisting of one connected set. If you only ask about the shortest trench without restricting yourself to trenches with at most n components this problem is, to the best of my knowledge, still open.

It is actually quite fun and usually leads to a lively discussion if you let the audience guess what these trenches should look like, probably with some support.

This problem can also be taken to the next dimension, by looking at the opaque cube problem, or any other shape you like. Also there are different stories one could choose to introduce this problem.