I'm using Mandrake at the moment, and I'm not finding it too "easy"! I'd say get something like Mandrake or Redhat first, find out if you like the ideas behind Linux (i.e. do you like doing many things the hard way, but getting lots of pleasure out of it?), and then progress onto Gentoo or Slackware or something else that'll take you a few days just to install. I want to get on to something like that eventually, but I think I'd just make a big mess if I tried now.

If you just want a taster of Linux, then try Knoppix. People usually say good things about it from what I've seen. You can just boot it off the CD without the need to install anything, so that way you can get an idea of what Linux is about without partitioning your hard drive and installing (or attempting to install!) a distribution.

www.distrowatch.com is a good place to learn about all the different Linux distributions.

Just remember: Linux is a challenge... as I'm finding out! But it's one that I'm enjoying. It just depends what you want out of a computer.