What about some large-number phenomena? This seems to be something the general public would appreciate and could relate to the "Computers in Modern Mathematics" booth others have suggested.
What I have in mind is not really Ackerman function/Graham's number business (which I don't think I could wrap my head around any more easily at a museum), but facts that involve small-ish large numbers. For instance:
The smallest positive integer $n$ for which $n$ divides $2^n-3$ is $4,700,063,447$.
There are many other great examples (though not all interesting or accessible to non-mathematicians) in answers to this MO question. It also might be nice to see comparisons of smallest counterexamples like this to 'real-world' numbers like the population of China (~$1.34$ billion), or the number of cells in the human body (~$10^{14}$), or the number of elementary particles in the observable universe (~$10^{80(\pm10?)}$).
To me, the goal of such an exhibit should be (1) to provide a few examples (like the one above) illustrating the importance of proof over verification of the first $10^{10}$ cases, and (2) to help museum-goers conceptualize the small-ish large numbers that come up in analyzing real-world phenomena.
