I must admit I started with Mandrake 10.1 community (Mandriva or whatever it is now), and whilst mandrakesoft did have a pay-based update system, there is also URPMI, which i found very easy to set up using
Easy URPMI. This is pretty good for newcommers, but i do personally prefer APT, having used debian-based distros. Depending on how good your patience is, and how good your net connection is, get a few "easy to use" distros. Things to look into (with my personal experiences):
Mandrake (Nice, reasonably stable, very easy to use. Nice installer and bootscreen)
Fedora - the new Red Hat (This was good also. Much like mandrake)
SuSE (although updates were quite poor and hard to set up IMHO, but nice installer. Incredibly easy to use, more so than mandrake.)
Debian (nice)
Mepis, Ubuntu (nice, based on debian: but still rough around the edges)
Knoppix-based live cds (although installable) are nice also, one to look for is XFLD. I haven't tried knoppix but XFLD detected almost everything, and worked fine with my troublesome wireless adapter, the netgear WG511).
Gentoo- maybe not a beginner system, but you do actually learn a lot even from a failed install, which will help you with most distros.
Whoah there's a lot there. Another one (which i am about to try) is Slackware. I've heard many recommend this for newbies despite it's allegedly complex install.
The best advice i can give is try a few. I checked out
distrowatch for a while, although to be honest this wasn't that helpful. It's a hard choice. There is tonnes of choice, too much really. One thing i found odd compared to windows, which i am assuming (maybe wrongly) you came from, is that with a live cd such as mepis; it is odd to be instant messaging whilst installing an operating system. Maybe it is just me, but with a live cd, time I would have wasted can be used to explore it. It also benefits from being debian based, and so it features APT.
As marghorp rightly said, "it is an experience which changes you." But get a distro you like. You don't know if a distro you haven't tried is any better. So try it (subject to your connection being ok). Not even six months in, and i've tried many distros (more than 10). :s maybe there's something wrong with me.