Right after you install it?
It's a matter of taste. Probably Mandrake or a small distro that is specificly designed to be a desktop enviroment.
Your options for customization is endless. I am sure that your aware of the special shells people have created for Windows and such. Take that and multiply it by 20 and then you almost get to the level of customization that is avaible thru X windows and Linux (doesn't even have to be linux, it can be any common open source operating system like FreeBSD or whatever). Most Linux geeks spend a couple days here and there (not constantly) tweaking different themes and behaviors once they start figuring out how to customize everything. It's kinda like a customized hotrod, or whatever, just a lot less messy and cheaper.
gentoo screenshots from Gentoo developers.
You can have it Window style setup, or a Mac style setup, or a classic Unix style setup, or your own very customized setup.
enlightenment screenshots
afterstep screenshots
The only thing is the confusing terminology, which after you understand a bit on how X works, it begins to make sense. It's all in layers, a software stack so to speak.
X Server is the program that takes care of the input devices (keyboard, pointer device (usually mouse)), and the output (video card, monitor). It "serves" your input to various X clients, which may be on your local computer, or on a LAN, or even on a server in some other part of the word. That's what is called "network transparency". For example I use evolution at home, but if I want to check my e-mail and I am at a friends house or at work I can ssh into my desktop at home and open up evolution so that it appears on my local "X server". Running it over a network can cause a big slow down in how the apps are drawn, though. Examples are: X.org server, XFree86 server.
XFree86 was used for years and years, until recently X.org forked off of XFree86 and using the same code base created a rival X Server that most everybody uses nowadays.
Programs and such are "X clients". With out any clients your X server appears to be this ugly gray black/white checkerboard affar with a ugly X shaped cusor.
Then on top of that you have your window manager. This program controls the actions and behavior of the windows and provide basic menus and controls what happens when you click on window borders and such. That's why it's a Window manager, it controls Windows. Examples are Afterstep, Enlightenment, TWM, IceWM, Metacity, Fluxbox, etc etc.
Then on top of that you have your regular X windows apps such as Firefox Browser or Xterms (provide command line interface).
Lots of times people use Desktops Managers such as Gnome or KDE. These are a collection of applications, panels, menus and behaviors that are used to provide a unified look and feel. They provide all the nessicary applicaitons to make a standard Desktop enviroment: such as Small games, browsers, e-mailers, office productivity tools, xterms, file managers (like nautilus or Konquerer), instant messanger apps, etc etc.
kde screenshots
gnome screenshots
For instance the standard Gnome desktop consists of: Nautilus filemanger, Metacity Window manager, Gnome-panel, Evolution e-mailer, Totem media player etc etc. I like Gnome personally, however I generally replace Metacity Window manager with OpenBox window manager, which is a gnome-complient manger that follows more of the look and feel of Fluxbox/Blackbox family of Window managers, which in turn are modernized versions of classic Unix window managers such as Twm or Fvwm.
However Desktop enviroments provide a lot of bloat and will require similar computer resources as Windows XP. However more minimalist enviroments like IceWM can reduce this need quite a bit and people even use them on embedded and low resource enviroments such as X Windows-enabled handheld devices.
But the whole idea of what is pretty, is very very subjective.