If you are willing to sacrifice the non-trivial deterministic requirement, then I would suggest the Deutsch-Jozsa problem. To summarize: you are given a black-box $f: {0,1}^n \rightarrow {0,1}$ it is promised that either $f$ is constant or balanced (i.e. $|f^{-1}(0)| = |f^{-1}(1)|$). You have to tell me which it is. The randomized algorithm works exponentially faster than the deterministic one, and has small error.
The best feature is that if you want to continue and mention quantum algorithms, you can do so to recover an error-less algorithm.
