In linux there are two primary things which affect the looks - the window manager (which is responsible for the window borders, taskbar, etc) and the display toolkit, which will determine how the actual "windows" look, the style of buttons, menu's, scroll bar etc. The big advantage is that you can customise each of them individually ...
A Desktop Environment like Gnome or KDE is a combination of window manager and a set of integrated applications built around the same toolkit (generally).
Changing the DE will pretty much give a complete new look to your GUI, so some environments to try out would be KDE, XFCE, Gnome, XPDE (XP like).
These in turn can be customised with themes etc... see
http://www.kde-look.org/ for KDE themes.
If you want to try individual Window Manager's, some good ones to try are enlightenmant, the windows 95 style icewm, the simple fvwm etc.
You can also customise the toolkit for a different look, the most common toolkit is GTK+ (used by gnome and many applications).
So make a choice on the desktop enviroment / window manager, and then look for themes for it
