Uriel Feige has shown in 1995 in his paper "A Tight Lower Bound on the Cover Time for Random Walks on Graphs", the following result:
For any graph $G$ on $n$ vertices, and any starting vertex $u$ $$E_u[G]\ge n\ln{n}+o(n\ln{n}).$$
Here $E_u[G]$ denotes the cover time, that is, the expected number of steps that it takes a walk that starts at $u$ to visit all vertices of $G$.
Let $C_u[G]$ denote the number of steps that it takes a walk that starts at $u$ to visit all vertices of $G$. In that case, $E_u[G] = \mathbb{E}(C_u[G])$. Say that an event occurs with high probability (or whp) if it's probability tends to $1$ when $n$ tends to $\infty$. Clearly, if for a vertex $u$, $C_u[G]\ge n\ln{n}+o(n\ln{n})$ whp, then $E_u[G]\ge n\ln{n} + o(n\ln{n})$. However, the opposite does not follow.
Still, is it true that the following (stronger) result holds?
For any graph $G$ on $n$ vertices, and any starting vertex $u$ $$C_u[G]\ge n\ln{n}+o(n\ln{n})$$ whp.
If not, is there any non-trivial lower bound for general graphs? For specific graphs? It is known, for example, for the complete graph $K_n$ (this is simply a coupon-collector problem).
