You know, it's funny. As I was reading along, I kept thinking, "Kline for Calculus." And there it was at the bottom! It's a good choice, indeed. I don't know Poole's book on linear algebra, so I can't approve or disapprove.
In terms of logic, I'd say that a knowledge of formal and informal logic helps the math student everywhere, sometimes even in intangible ways. I would recommend Copi and Cohen's Introduction to Logic for the informal logic. I'm not a huge fan of their symbolic approach, however. For that I'd recommend Barwise and Etchemendy's Language, Proof, and Logic. Their take on the natural deduction system is very nice, I think. It's easy to remember, at any rate!