I found Knuth's Art of Computer Programming a bit too dense for me, and I have a high tolerance. There's definitely a wide world inbetween the fluffy Skiena and the concrete Knuth.

(I did enjoy Concrete Mathematics.)

Knuth is a bit too imperative for my interests.

But if you like strong stuff, Schrijver's "Combinatorial Optimization: Polyhedra and Efficiency" tells you more about P and the boundary to NP than you ever wanted to know.

http://jeffe.cs.illinois.edu/teaching/algorithms/ is reasonably accessible so far for me, yet still manages to teach me new hard things.

None of the books mentioned are bleeding edge. It's easier to get that out of papers.

If you haven't tried the latest entries in Knuth's work, I'd recommend those. The preprints of the Dancing Links stuff is surprisingly approachable and a ton of fun.