New books are coming out all the time, but here are two big ones that stick out in my mind (perhaps because I've seen the authors recently). [Feel free to mention others worth noting in the comments.]
Recently available (I saw copies at FCRC) is The Design of Approximation Algorithms (Amazon link) by Williamson and Shmoys. Here's a link to the book page. (All books have web pages now, don't you know.) An up-to-the-moment books on approximation algorithms by two well-known experts.
Coming soon is The Nature of Computation (Amazon link) by Cristopher Moore and Stephen Mertens. Here's a link to the book page. About 1000 pages of introduction to computer science (with some statistical physics, and maybe some other physics, mixed in), with lots of problems. I've seen a preview of the text and it looks like an interesting read. (I'm curious if people will use it for courses -- if you have or are considering it, let me know.)