It really depends a great deal on the intended audience. What is their expected mathematical background? Is this likely to be their first exposure to mathematics that isn’t primarily computational? (Standard first-year calculus, as it’s usually taught, is primarily computational.) Are they likely to go into mathematics, or are they more likely to go into computer science? In a related vein, is the course intended to have an applied bias? Is it intended, as such courses sometimes are, to be an introduction to theoretical mathematics?
As far as I’m concerned, there are only two clusters of ideas that are absolutely indispensable in a first course in discrete mathematics. One is the basic counting techniques of elementary combinatorics; the other is recursive definition and proof by induction. The natural point of contact of these two clusters is the solution of recurrences. The basic theory of homogeneous linear recurrences is accessible, and one can also deal at this level with first-order non-homogeneous recurrences that are simple enough to be ‘unwrapped’. (Rigorously proving that the solution found by unwrapping really is the solution gives more practice in proof by induction.)
Beyond that a great deal depends on how much time is available. In a typical U.S. semester I’d expect to be able to do a decent job with one or maybe two more topics, depending on the calibre of the students. I’ve usually chosen either to do a bit with formal languages, concentrating on regular languages, regular sets, and finite-state automata, or to do some graph theory.
I don’t really care for the kind of comprehensive text that you seem to be contemplating: either it contains far more material than can be covered in one course, or it gives a very inadequate introduction to a wide range of topics without actually doing anything very worthwhile with any of them. The latter is useless. The former is acceptable if the people using it understand that any given course will be only a selection of topics from the text, and it may be necessary if the text will be used by different instructors for different kinds of audience. Still, I prefer a more focussed text.
I also think that most elementary discrete mathematics texts do far too much formal logic. In my experience it does not help students learn to read and write proofs and is largely a waste of time. Similarly, it’s very easy to get bogged down in basic set operations and relations and functions; beyond whatever bare minimum is actually needed, these really belong in some other course.