O'Reilly's Statistics in a Nutshell is a good stats textbook and reference, has some good exercises to be done in R (or S or Matlab), and is generally more programming-oriented than most statistics treatments. http://oreilly.com/catalog/9780596510497/
Two important classics are Knuth's The Art of Computer Programming (more algorithms/programming-focused; very steep learning curve) and Concrete Mathematics (with Ron Graham and Oren Patashnik; more math-focused; may be easier for self-study). Both have exercises you can work through, though many of the exercises are proofs (not easily translatable to programming).
I cannot tell you how frustrating this was for me. I wanted just the meat: the core mathematical concepts on which statistical models and inferences are built. Don't tell me a folksy story about gathering soil samples, show me the tools and what they can do, both their power and their limitations. I can think for myself about how to apply those concepts.
I loved this book for being exceptionally clear and terse. I was hooked from the first sentence: "Probability is a mathematical language for quantifying uncertainty." That one sentence makes the concept clear in a way that the entire chapter on probability from "Statistics in a Nutshell" (http://www.amazon.com/Statistics-Nutshell-Sarah-Boslaugh/dp/...) did not.
I'm not someone who thrives on theorems and proofs, I thrive on concepts. And I found this book dense with clear explanations of the key concepts.