The consensus on CM tool choice is simply, "pick one that's comfortable for you and your team," and, "it doesn't matter which one you use, just be sure you're using configuration management." It's definitely better than dealing with shell scripts, since a lot of things you write in your CM language gets abstracted automatically for whatever operating system you're using (this is the biggest takeaway - you really don't want to rewrite shell scripts just because you've decided to add a different Linux distro or UNIX in your network.)

I've used both Puppet and Chef extensively, and they both do the same thing, they just go about it differently. (shameless plug of a blog post I wrote that compared the two: http://redbluemagenta.com/2011/05/21/puppet-vs-chef)

Also, it's almost always about how you approach configuration management - thankfully, with Puppet and Chef, you don't have to manage everything on a system in your CM right away. If you have to manage SSH authorized_key entries and it's getting annoying to do it by hand, then write a Puppet module / Chef cookbook to manage it for you. Then go on to manage /etc/hosts entries, then to deploying packages... you'll hit a point where you can reasonably rebuild a server from scratch without thinking about it.

There's other CM systems out there too: bcfg2, cfengine, etc.