Everyone always recommends Ubuntu to newbies to the point that it's becoming the AOL disk of Linux.

It really depends where they're coming from. If they're Windows users, something with a default KDE desktop might be much better suited for them - in fact, KDE is more similar to Windows 7 than Windows 8 is to Windows 7.
But you are right that one can (and should) try more than one distro at first. My early mistake was going for a rolling release distro first.

What I liked about the last one I tried - OpenSUSE - was that the install DVD offered KDE, Gnome, LXDE, and XFCE as desktop choices so you could easily try out the different desktops. It also installed several PDF manuals including a quick start guide to KDE, to LibreOffice, etc. as well as more advanced manuals on security and system optimization. The installer was very pleasant to use and smart enough to find my Windows partitions and offer to mount them correctly in Linux, which made the transition easier as well. In fact, I started "testing" OpenSUSE and a year later I realized I was still running my "test" without having gone back into WIndows.