I've been evaluating textbooks to use in the intro programming course I teach in the fall, and I think I've found the one I'm going to use: Programming in C by Stephen G. Kochan. I've read the first few chapters, and I really like the style: concise, clear, with code examples that are short but illuminating. I have a huge pet peeve with programming textbooks that are 800 pages long and are so filled with unnecessary detail that you can't see the forest for the trees. (I won't mention names, but I'm sure you know what I'm talking about.) I actually evaluated K&R (2nd ed.), but I was quite disappointed. I would not want students (or anyone really) to write code in that ultra-terse, cryptic style. The Kochan book gets it just right: focused prose, clear code with meaningful (but not excessively long) identifiers.
Parallel to this discussion, of course, is the question of why I want a book that just does C (as opposed to C++). There are two main reasons. Students need to be exposed to low-level concepts like pointers and addresses, so either C or C++ needs to be in the curriculum. Second, C++ is a dangerous, bloated mess of a language when you get to the object-oriented features. My experience has been that students' initial transition from C to Java is a fairly easy one, especially if they have seen structs and are comfortable with the concept of encapsulation. Once they know Java, the sky's the limit; due to the safety features, clean object model, and availability of outstanding development tools like Eclipse, it really is an excellent language for CS education.