I had gentoo purring on my pentium II 333 mhz with 64 mb mem when a friend of mine bought it and I had to wipe that and install Windows 98 SE.
You might want to avoid gnome and kde and go with a lightweight wm instead if you want any speed in X with Redhat. I suggest fluxbox.
Mandrake has packages compiled for i586 (Redhat uses i386 packages) so will run faster than Redhat. How big is the hard drive you are planning upon using?
What modem/video card/sound card are you planning on using? You might check and see that they are supported.
Linux Hardware Compatibility HOWTO