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.
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.