Casella & Berger's "Statistical Inference" is a nice introduction to basic probability theory and statistics. I found it pretty readable, and it's used for many 1st year graduate stat programs.

Duda & Hart's "Pattern Classification" is one of the best introductions to machine learning IMO. It assumes very little in the way prerequisites, which is nice for first time exposure.

Hastie & Tibshirani's "Elements of Statistical Learning" can be a little intimidating without having been exposed to the ideas of the previous two texts. Afterwards, however, it is a gem.