Most mainstream calculus books suck; they tend to hedge their bets between being advanced and proof-based on the one hand, and catering to students with a mediocre grasp of algebra on the other. Thomas' book is probably the best of this bunch.
Epp does proofs and discrete math, and a little bit of algorithms. The usual favorite for algorithms is Cormen et al.'s Introduction to algorithms, although I don't know it well.
For linear algebra, Axler (as someone else mentioned) is a very nice book. I really like Knop also (more beginner-friendly). Hefferon's Linear Algebra looks very nice, and is (legally!) free online. If you prefer a more applied/computational bent, try Strang.
For linear algebra, it depends heavily on your choice of book. To read Hefferon or (even more so) Axler, you'll want to have seen a fair amount of mathematical formalism, and read through some proofs. Knop is probably a good place to learn mathematical formalism; if you approach it with limited background it will be slow going but you'll learn a lot.
A book which I have found excellent is Epp's Discrete Mathematics with Applications. The book is very patient and explains things really well -- stuff like formal logic, induction and recursion, proofs, probability and combinatorics. Lots of good exercises too.
I used this as a textbook in a course required of all of our sophomore CS students. It lays an excellent foundation for more sophisticated material that follows.
The latest edition is absurdly expensive (as is the case with most textbooks), but used copies of previous editions are likely to be ubiquitous on Amazon and elsewhere.