Which randomized algorithms have exponentially small error probability? Suppose that a randomized algorithm uses $r$ random bits. The lowest error probability one can expect (falling short of a deterministic algorithm with 0 error) is $2^{-\Omega(r)}$. Which randomized algorithms achieve such minimal error probability?

A couple of examples that come to mind are: 


Sampling algorithms, e.g., where one wants to estimate the size of a
set for which one can check membership. If one samples uniformly at
random the elements to check, the Chernoff bound guarantees an
exponentially small error probability. 
The Karger-Klein-Tarjan algorithm for computing minimum spanning tree. The algorithm picks each edge with probability 1/2, and recursively finds the MST in the sample. One can use Chernoff to argue that it's exponentially unlikely there'll be 2n+0.1m of the edges that are better than the tree (i.e., one would prefer to take them over one of the tree edges).


Can you think of other examples?

Following Andras' answer below: Indeed, every polynomial time algorithm can be converted to a slower polynomial time algorithm with exponentially small error probability. My focus is on algorithms that are as efficient as possible. In particular, for the two examples I gave there are deterministic polynomial time algorithms that solve the problems. The interest in the randomized algorithms is due to their efficiency.
Impagliazzo and Zuckerman proved (FOCS'89, see here) that if a BPP algorithm uses $r$ random bits to achieve a correctness probability of at least 2/3, then, applying random walks on expander graphs, this can be improved to a correctness probability of $1-2^{-k}$, using $O(r+k)$ random bits. (Note: while the authors use the specific constant 2/3 in the abstract, it can be replaced with any other constant greater than 1/2.)

If we take $k=r$, this means  that any BPP algorithm that achieves a constant error probability $&lt; 1/2$, using $r$ random bits,  can be (non-trivially) improved to have error probability $2^{-\Omega(r)}$. Thus, (unless I misunderstood something), the error probability of $\leq 2^{-\Omega(r)}$ is achievable for every problem in BPP.