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.
https://en.wikipedia.org/wiki/Goodstein%27s_theorem
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).