It really depends on what you're looking for. If you're trying to build a solid understanding of algorithmic patterns, the Algorithm Design Manual is a quite good choice, and not hand-wavy nor lacking in rigor in any meaningful way.
If you are trying to prove properties of particular algorithms or you already have a specific algorithm in mind that you're considering using and need to analyze its complexity, then this would not be the best choice.
You shouldn't dismiss/denigrate the book because it doesn't fit with your personal use case.
The whole 'lacking rigor' idea here is a common pitfall for programmers—seems predicated on the false idea that coding is this one dimensional activity with a hard side and a fluffy side, and the fluffy side is largely comprised of deceptions for the weak or timid. I bet there's a strong correlation between folks who prefer (e.g.) Cormen to Skiena and those who insist on using terminal windows and vi/emacs for every task—and yet the correlation you might hope to find with the quality/depth/interest of their work fails to hold.
I always feel kind of bad when I see programmers taking on this attitude (often times it manifests as they're trying to freak out more novice programmers and display their supposed superiority), and unnecessarily hampering themselves. It's one aspect of our culture I'd really like to see die out before it spreads to the next generation.