kde-look.org has all the goodies you need to configure KDE to your own needs. You can change your icon theme, window decorations, style etc. Take a look at my screenie for what you can do with the artwork and apps from kde-look.
As for gnome, you can't configure it as much as KDE. There are good themes at gnome-look.org and art.gnome.org.