When I think about textbooks and other books, I usually ask myself some questions:
The following books aren't going to give the absolute beginner a simple enough start, but if you already know about variables, ifs and loops, or know another programming language and want to learn Java, these are good books.
It passes all the tests. Even the one bad review in Amazon was mostly just disagreement about terminology (eg, the first chapter should have been called a brief review, not a crash course; javadoc should have been a described as a implementation tool more than a design tool). I'm not sure about the negative multi-threading comment.
I've extracted many of the books from this list, and kept those that I like too, or added warnings to others that might be a problem. I've also put them in categories.
More at www.javalobby.org/articles/5books/full.jsp