Of the top of my head,

- Machine Learning by Tom M Mitchell http://www.cs.cmu.edu/~tom/mlbook.html

For general reading and introductions I also like:

- Pattern Classification by Richard Duda

- Pattern Recognition and Machine Learning by Christopher Bishop

For a bit more emphasis on statistics and math, I usually dive in to

- Classification,Parameter Estimation and State Estimation by van der Heijden

And last, but certainly not least:

- Information Theory, Inference, and Learning Algorithms by David MacKay, available here:

http://www.inference.phy.cam.ac.uk/mackay/itila/