The major difference is how they manage their files. I can only speak from a Debian prospective, but there is a command called "apt" which you will use to install/deinstall programs, upgrade your entire computer and more.
In Debian, everything is controlled in configuration files, of which the folder /etc will be your favorite place to go.
Both can be pretty challenging for a new user. You could look up Ubuntu of Kununtu (both essentially the same but Kubuntu is more like Windows, and Ubuntu is kind of like Mac)
Both of these are based off of Debian, but they have a more rapid release cycle. I use Debian on my servers, and Kubuntu on my desktop and laptop.
research will be the key to your decision. Visit distrowatch for more info:
www.distrowatch.com
also, google fedora for RedHat and Debian or Kubuntu...many sites will have screen shots and good documentation.
One last thought:
when you partition your computer, make a separate /home partition for your personal documents. Then you can format/install over the rest of your computer without touching the important stuff. This can help you experiment with different Distros.

I hope that is enough for now
