You've already done it once, and lived to tell the tale.
Actually, you've done all the hard work already... Taking disk space away from Windows without killing it so you have someplace to install Linux.
As long as you are OK with killing off the RedHat install, it will be easy... Just start the install. When you come to the part where you need to create partitions, delete the RedHat partitions, and create the new one in the now-empty space. As long as you don't do anything to the NTFS partition, you should be OK. (Should be... I make no promises, guarantees, or warranties about this statement. As always, I suggest backing up any data you cannot replace.)
If you were booting the system with GRUB or LILO, tell the Debian install to take control of the booting. It will set-up the conf file and redirect the MBR, if need be, and it should take over without a hitch. If you were booting with NTLoader, then don't let Debian take over, and edit your settings after install.
Hopefully, all will go well. Debian can be a bear to install, though, so you might want to read any articles, HOW-TOs, or install instructions that you can find. You might even want to restore the MBR to boot straight to Windows, just in case it takes you a couple install tries.