Algorithms with superexponential runtime?

I was talking with a student the other day about the common complexity classes of algorithms, like O(n), O(n^k), O(n lg n), O(2ⁿ), O(n!), etc. I was trying to come up with an example of a problem for which solutions whose best known runtime is super-exponential, such as O(2²ⁿ), but still decidable (e.g. not the halting problem!) The only example I know of is satisfiability of Presburger arithmetic, which I don't think any intro CS students would really understand or be able to relate to.

My question is whether there is a well-known problem whose best known solution has runtime that is superexponential; at least ω(n!) or ω(nⁿ). I would really hope that there is some "reasonable" problem meeting this description, but I'm not aware of any.