Maybe the 3n+1 problem? It's definitely easy to understand in a few seconds, and definitely fiendishly hard. I'm not sure if it seems easy to solve though :)
Another one that came to mind is about efficiently computing the permanent of a matrix[1]. Maybe understandable in seconds if you know how determinants work.
3n + 1 is interesting because it seems so tantalizingly easy and beautiful at first glance. Its like looking at a stream where you can clearly see the stony bed and it appears to be ankle deep but once you take a step you realize the lighting has fooled you and you fall head over heels into icy waters.
It's so much more interesting if you happen to know about the "hydra game" (the Goodstein theorem), which is also a question about sequences and their termination at 0.
But this is easily proved (using infinite ordinals, but it seems it could be proved just by coming up with a similar concept like the infinite ordinal arithmetic, basically providing an upper bound for each step of the algorithm and showing that there's an eventual maximum to these and then there's a monotonic decrease, and that the number of steps are always finite).
Maybe the 3n+1 problem? It's definitely easy to understand in a few seconds, and definitely fiendishly hard. I'm not sure if it seems easy to solve though :)
Another one that came to mind is about efficiently computing the permanent of a matrix[1]. Maybe understandable in seconds if you know how determinants work.
[1] https://en.wikipedia.org/wiki/Computing_the_permanent