BloggoSuction
I enjoyed my outing with BlogSkins - not difficult, but you need to set aside some time to add your links and other toys back into the template when you're done (and to mess around with where to put them to make things look passable). Definitely back up your old template beforehand, as applying a BlogSkin is like a "clean install." Also, only a few of the Skins have an archive page counterpart. This means if you have a separate archive page, it will still appear in the old format until you select and apply an archive skin (which may not match your main page, as there only are a few archive skins posted now). The other "skinning" tool I've looked at that has some interesting templates is Blog Designs. It's the same idea - an open-source forum for designers to submit their work for non-commercial use by the likes of us. Unlike BlogSkins though, these aren't set up to give you a direct substitution of your Blogger template. I think you download the code and do a cut-and-paste job instead.