For which algorithms is there a large gap between the theoretical analysis and reality?
The most glaring example is of course the Simplex method that runs quickly in practice, suggesting poly-timeness, but takes exponential time in theory.  Dan Spielman just got the Nevanlinna award to a large extent for explaining this mystery.

More generally, many instances of Integer-programming can be solved quite well using standard IP-solvers, e.g. combinatorial auctions for most distributions attempted on significant sized inputs could be solved -- http://www.cis.upenn.edu/~mkearns/teaching/cgt/combinatorial-auctions-survey.pdf