Don't worry about speed, your machine will probably be fine. (I still use Linux on a P-166 ;-).
For a list of hardware supported by Red Hat, see http://hardware.redhat.com/hcl/
Typically, if you have a winmodem, your distribution will not come with software to support it. To get software to support your modem, download it from http://www.linmodems.org/
I would recommend Red Hat over Mandrake, but that's just a matter of personal preference. Try 'em both if you want. Other great distros are Slackware (my favorite, but not necessairily a good choice for all newbies) and SuSE (a very good choice for newbies, I'd recommend it over both Red Hat and Mandrake).
If you buy a copy of whichever distro you choose instead of downloading it, you get manuals, including an install guide. I _STRONGLY_ recommend that you do so, at least for your first Linux install.
You will be given a chance to partition your hard drive during the installation process. If you don't have any unpartitioned space (space you can access with Windows is part of your Windows partition(s) even if it is reported as empty space) you will need to modify your Windows partition to make room for Linux. Most install programs are not set up to handle this, so you'll probably need to do it yourself before attempting to install Linux. This is a slightly risky process, so back up anything important you have first. The first step (after backing up important files!) is to defragment the disk. This will move all of the data to the beginning of the partition so you can take more space from it (think of it like shaking a cup of flower to eliminate air pockets). The Windows built-in defragmentation tool will be fine for this. Next, you need to use a program that can shrink the Windows partition. A good program for this is Partition Magic, but it isn't free. A free program you can use is fips, which is available at http://www.igd.fhg.de/~aschaefe/fips/
PLEASE read the documentation for fips before running it on your system. If everything went will with fips (or Partition Magic), you will now have a smaller Windows partition and some unpartitioned space, then you are ready to install Linux.
If shrinking your Windows partition sounds scary, an alternative is to buy a new hard disk and put your Linux partition on that. If you do this, you will still need to write your bootloader to the MBR of your primary disk, but this is the only thing that will be written to your Windows disk. If you don't even want to do that, you can make the Linux disk the primary or use a floppy disk for booting into Linux.
If all of this talk of partitioning is making your head spin and you can't get a new hard drive, another option is to go with SuSE Linux, which can be installed to share a partition with Windows (the files go under C:\linux and you use loadlin.exe to start Linux).
Many Linux User Groups hold events called installfests, which is a gathering to help newbies install Linux. If you're looking for someone to help you through the install, see if your local LUG is holding an installfest any time soon.