In terms of a desktop distribution, go Mandrake. Sure, it's not 100% stable and doesn't have the Bluecurve look of RedHat, but the it looks great and works. I currently have 3 computers running, among which is a laptop. Mandrake was able to pick up all the hardware on the laptop without a problem, and has tons of software. Plus PLF provides a lot of extra multimedia packages that really help. I've found RedHat 8 (which I tried) to not work as well and to be harder to use. Plus Mandrake does a really good job with KDE, while redhat concentrates more on Gnome, and since I prefer KDE, I tend to not like RedHat as a desktop distribution.
On the other hand, go with RedHat for a server (unless you want to deal with debian/gentoo/whatever). RedHat is solid, rarely crashes, and is more or less the standard. There are tons of RPMS for it, and personally I've had great success with it as a server.
For a router, it really depends on how much time you have and what you need. If you want to use an old computer, RedHat is easy to install and will work. Personally, my third computer is a router based on a VIA EPIA MB that is 100% silent. It does IPsec routing from one location to another (connects to my server), and boots off a CF memory card. I built my own system from Linux from Scratch, and have a pretty lean install (177 MB, although I never cleaned out alot of the junk from it). its currently been up for 37 days, so I'm pretty happy with it (never crashed before, just had to shut it down a couple of times), but it did take a long time to get everything working properly, so its your decision on whether you want to do this.
-David