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.
http://www-stat.stanford.edu/~tibs/ElemStatLearn/ or straight to the PDF at http://www.stanford.edu/~hastie/local.ftp/Springer/ESLII_pri...