* Calculus by Spivak. This was used in my intro calculus course in university. It's very much a bottom-up, first-principles construction of calculus. Very proof-based, so you have to be into that. Tons of exercises, including some that sneakily introduce pretty advanced concepts not explicitly covered in the main text. This book, along with the course, rearranged by brain. Not sure how useful it would be for self-study though.
* Measurement by Lockhart. I haven't read the whole thing, but have enjoyed working through some of the exercises. A good book for really grokking geometric proofs and understanding "mathematical beauty", rather than just cranking through algebraic proofs step by step.
* Naive Set Theory by Halmos. Somewhat spare, but a nice, concise introduction to axiomatic set theory. Brings you from nothing up to the Continuum Hypothesis. I read this somewhere around my first year in university and it was another brain-rearranger.