I teach such a course to mathematics majors, a somewhat different audience, and I find there are always some who are little unclear about "if-then" vs. "and", quantifiers, and free/bound variables. I mean that in a practical sense -- they confuse themselves, "accidentally" as it were. Theoretical instruction in formal logic helps only a few; they need examples to clarify formal logic, at which point formal logic might be useful to them.
I teach the formal stuff and proof structures and so on, but I have to keep in mind the pitfalls above that my students are facing. I haven't thought about what examples can be shown with sudoku, but it seems a good thing to use, if you can create good examples with them. (It will be fun for many of them, but don't be surprised if not all find it so. It's a hard criterion, to please everybody.) Now you're talking about proof by cases and proof by contradiction, but the pitfalls I mentioned seem more elementary to me. They seem like they should be addressed before getting to cases and contradiction. Probably that can be done with sudoku. (I'll give an example of mine later.)
My main point here is to be aware of what problems your student might face and to smooth the way for them, if only a little, before they stumble on them. If this is your first time teaching the course, expect to learn a little of what you wish you had known about your students before you started. I don't have any definite view about whether you should start in Chapter 1 or Chapter 2 -- I wouldn't even if I knew the book, which I do not at all (a preview is not available on amazon). I think it could be done either way, especially if your colleagues are suggesting to start in Chapter 2. The way I imagine that could be successful is that by using concrete examples in number theory you can illustrate the logical principles that may or may not be presented somewhat too abstractly in Chapter 1. (There's no reason to think Chapter 1 has to be abstract.) The other main thing is to be confident in your approach. Don't do something that doesn't make sense to you just because someone else recommended it. It might turn out to have been good advice, but if you don't understand it, you probably won't do a good job with it. Sometimes the advice you get is incomplete: what is clear in the other person's mind is not entirely conveyed to you. (I've had that experience.)
How I start. All my students have had at least a year of calculus. Many of them are still quite good at calculus. So I use continuous functions and differentiable functions for examples. I ask them to come up with functions that are continuous (C) or not at, say, $x=1$, or differentiable (D) or not. I ask them how many combinations are possible and help them see all four, (C, D), (C, not D), etc. Now not all four are in fact achievable. Why? Someone will say because a differentiable function is continuous. Then we look at "$f$ is D and $f$ is C" and "If $f$ is D, then $f$ is C." Before addressing the implication, I make sure they all agree it is true (because it is a theorem, it has a proof). I put the examples they come up with in a table with the logical values T/F in columns for C and D. Then I go over the meaning of "and" and "if-then". The relation to the rest of the course, which you asked about, is this. I use and reuse the examples when we talk about proving "if-then", whenever confusion arises, and whenever I feel clarification is needed.
I also use other examples. Using a non-theorem is good for illustrating how to show an implication is false. A simple one is "if $x^2 > 4$, then $x > 2$", where $x$ represents an integer or a real number (but be sure to include negative numbers).
Even if those examples are not appropriate for your students, my hope is that it might give you an idea how to use the sudoko puzzles. Elementary number theory is also a good source of simple examples, which may be why it is the recommended starting point by the department.
