I was in the same sort of position when I decided to install redhat. It is a fun OS and you learn a LOT real quick. As far as installing on a 4 gig partition. What version of Redhat is it? 7.1? 7.2? I think they said if you are goign to install both KDE and Gnome (which I would do if I were you), you need 1.5 gigabytes of storage just for the install. It looks like 4 gigs would be enough if you aren't going to be using it too much. If you can spare an extra gig, I might give Linux 5 gigs.
As far as partitioning...Do you own partition magic? Or..would you be willing to do a clean install of XP? The easiest way to install Linux is to leave unpartitioned space on your hard drive. If you are using partition magic, it is really easy, just resize your existing partition by 4 or 5 gigs, and just leave it after it is done. Same goes with doing a clean install of XP...just partition your drive and leave 4 or 5 gigs unpartitioned on the end. When you install Linux, the installer will find the unpartitioned space on your drive.
There aren't really any 'rules' of NTFS/FAT32. Linux will be able to read and write to fat32 partitions quite easily. You just have to 'mount' the partition when you are actually installing Linux (If someone else can chime in and say where to mount it...I'd appreciate it. I am not at a linux box right now and forgot where I mounted it). You just need some unpartitioned space like I said above.
I just re-read your post on formatting the 8gb drive. If I were you I'd try this and leave your other (20 gb) drive untouched. As with everything though, there are about 15 different ways to install Linux. The way I did it was to install XP first and then have LILO (Linux boot loader) overwrite the MBR. All you have to do to get back to windows is add a line to /etc/lilo.conf (I believe).
Here is a link that will help you out. It is another forum
on redhats site about dual booting. Hope this helps!
p.s. Hope this make sense, its EARLY here! I am a little tired and this daylight savings time...it has really messed me up!