I think you make a nice point, but most of all I think you slipped in a better idea.
A good class in set theory and introduction to finite math and proofs would be the best. I am a graduate student in mathematics, and I see many math majors without a good background in set theory. Also, getting an early start with induction and simple proofs in combinatorics builds mathematical maturity very quickly. Additionally, it is easy to get students interested in combinatorics because the problems are so easy to understand and fun once you do.
Obvious Halmos' Naive Set theory is the one of the standards. For introduction to combinatorics, the book by Jonsenbaugh is pretty easy and it covers and intro to proof. I really like the combinatorics book by Brualdi but it might be a bit difficult.
If you are super brave you could read the book by Lawvere on an introduction to category theory...