ESL is a good book, but it should be mentioned that it is a significantly more difficult read than the other suggestions. Not at all an introductory-level text on ML.
Well, if you're willing to just follow the graphs and the argument the first time around, you can definitely get some use from it. I learned about classification, cross-validation and the bias-variance tradeoff from the first time I read it, and it significantly spurred me to deepen my understanding of the relevant mathematics.
for some reason the "bayesian reasoning and machine learning" (which to my eye is the most readable - perhaps because it is assumes the least from the reader) link is directly to the pdf. the site is at http://web4.cs.ucl.ac.uk/staff/D.Barber/pmwiki/pmwiki.php?n=... and includes a discount for the dead tree.
http://www-stat.stanford.edu/~tibs/ElemStatLearn/ or straight to the PDF at http://www.stanford.edu/~hastie/local.ftp/Springer/ESLII_pri...