themes
If you are going to stick with gnome, you can obtain eye candy either as individual bits or as whole themes from places like http://gnome-look.org/
http://ubuntusatanic.org/ for example has some interesting ideas and a simple explanation of how to load them.
Mostly you can use the package manager to suck them from repositories, like everything else.
If you are not going to stick with gnome, you can try things like
http://www.enlightenment.org/
http://www.afterstep.org/
after installing them you can just pick them as an alternative to your default gnome session when you log in.