As a newbie myself, I tried out about 20 different distros on my computer and always came back to Mandrake, RedHat and SuSE as being the best for my purposes. I was looking for a full replacement for Microsoft XP (as opposed to a distro where I had to continually reboot into Microsoft because I couldn't solve my problems) . Depending on what type of hardware you have, you may find that 'smaller distros' do not support your hardware.
If you want to have a play around with different distros, go ahead. If you are looking for a fast efficient switch to linux, then definately go with one of the three you listed.
Do you have a broadband connection with unlimited downloads? If so, then just download a bunch of distros and try them out. They only take 30mins to install. Have a look at www.distrowatch.com.
That should point you in the right direction.
BTW - I wouldn't worry too much about your concerns about the difficulties to install. They are all pretty straightforward. Certainly SuSE, Mandrake, RedHat are all exactly the same. Although some people will tell you otherwise.