Given that it’s for computer science majors, my first choice would be Susanna S. Epp, Discrete Mathematics with Applications, which meets all of your criteria except price. Among the standard discrete math texts it offers one of the gentler introductions to reading and writing proofs. Unfortunately, it’s obscenely expensive. Edward R. Scheinerman’s Mathematics: A Discrete Introduction is merely expensive and is in my opinion a significantly better book, but it’s aimed more at math majors than at computer science majors; still, I recommend taking a look at it. It also makes a serious effort to accustom the neophyte to reading and writing proofs.
I’ve also used the notes by Lovász & Vesztergombi mentioned in another answer; they have the great virtue of being free, and in general they’re well written, but there are few exercises, and they lack coverage of a number of topics that are pretty standard in discrete math courses for computer science students. You would probably have to supplement them fairly extensively. Here are some other freely available texts and lecture notes; I’ve not used them, so I prefer not to offer any judgements.
Added: In my experience Graham, Knuth, & Patashnik, Concrete Mathematics, is pretty much out of the question for students with no more background than Calc 1. I used it several times in an upper division course, with students who had had at least some exposure to theoretical mathematics, and a majority of them had trouble with it. The coverage is also rather idiosyncratic for a discrete math course for computer science students, and it certainly doesn’t include a chapter on logic and proofs.
Do you know yet what topics are to be central to the course?