I have a couple machines set up as you outline. It really s simpler than it sounds since you do not have to carefully partition a single HDD for two OS.
You should be able to boot with the installation cd or a boot and then root floppy. Both my machines boot nicely from my CD Roms using the Slakware 7.0 and 7.1 distributions. Intead of using setup, you will need to partition the HDD for LINUX.
On one machine, I use a Hard Drive which is attached to the secodary IDE channel as the Master. So it is not hda, nor hdb, but hdc.
To partition the drive boot into Linux. run fdisk /dev/hdc for the third IDE harddrive. My other machine, needs fdisk /dev/hdb since the Linux hard drive is the secon/slave drive on the primary IDE controller, or the second hard drive. (The CD Rom is the third, so it is hdc)
There is also cfdisk, another partitining utility that is more menu driven than fdisk. Of course REdHat also has Disk Druid which is mor like point and click.
Of course, this brings up several related issues, such as the size of the hard drive, swap partitions, toggling the bootable falg for the LINUX partition, and other issues. Most newer hard drives are large enough to have more than 1024 cylinders. Fdisk will mention it, but I have never had a problem with LILO booting these. Still, I usuall do take the trouble to figure out the way the bios translated the drives and use the expert functionality of fdis to change the Cylinders, Heads, and sector size to match what the bios reports with LBA enabled. (The BIOS does the conversion from normal to LBA for me for IDE Hard Drives. SCSI Hard drives depend on the SCSI controller so you have to do it yourself?!)
In fact, setting the CHS the same as the BIOS translation, LILO boots quite well from hdc3 (hdc1 and hdc2 are both swap patitions) despite the fact that hdc3 ends well past 1024 Cylinders.
Once you have that partitioning figured out setup should be simple. Some distributions run Liloconfig at the end, allowing you to configure the LInux LOader to boot as you wish.
It is simple if you follow the instructions step by step by step.