Combinatorics is even better: you can state a problem in ten seconds with a numerical answer that would take years to compute with supercomputers. For instance, find the Ramsey number R(5,5). Wikipedia says it's (an integer) between 43 and 49.
At first this may seem unfair, but it's parallel to tan(10^100) in that there's only computation left to do; the computation in this case being to check all possible colorings of complete graphs with some number of vertices.
Also, isn't GCD a rather poor example, being the one number theoretic problem that does have an efficient algorithm to solve?
R(5, 5) is hard to solve exactly, but easy to estimate: 46 is correct to within 10%.
(Although perhaps only Feynman could produce such an estimate in ten seconds, without knowing the range beforehand.)
I have a whimsical challenge for you: come up with problems with numerical solutions that are hard to estimate.
This, like surprisingly many things, originates from a Richard Feynman story:
So what would you ask Richard Feynman to solve? Think of this as the reverse of Fermi Problems.
Number theory may be a rich source of possibilities here; many functions there are wildly fluctuating, require prime factorization and depend upon the exact value of the number rather than it's order of magnitude. For example, I challenge you to compute the largest prime factor of 650238.
(My original example was: "For example, I challenge you to compute the greatest common denominator of 10643 and 15047 without a computer. This problem has the nice advantage of being trivial to make harder to compute - just throw in some extra primes." It has been pointed out that I forgot Euclid's algorithm and have managed to choose about the only number theoretic question that does have an efficient solution.)