Personally I have been on Redhat since the first time I used linux although I have had some exposure to Suse. I think you can start with any. Make sure that you get to see others too cos if you want to learn much, you cannot afford being a "fanatic" of 1 distro.
Have fun..linux is great(I think)