MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 1 [made Community Wiki]

http://www.amazon.com/How-Prove-Structured-Daniel-Velleman/dp/0521675995/ref=sr_1_1?ie=UTF8&qid=1303491885&sr=8-1

This text was used in the "Math Structures" class at my undergraduate institution (basically an intro to proof writing) and I found it really useful for transitioning from calculus type problems to constructing proofs. I think it meets all your requirements (definitely the first two, and I don't recall there being a great deal of historical\philosophical digressions).