As for whether a CCNA or RHCE is the best complement to the MCSE, please recognize that obtaining an RHCE requires a great deal more time, expense and effort than earning a CCNA. Thus, the two credentials aren't really comparable. And because the RHCE is a great deal more valuable than the CCNA, that also means the RHCE wins this contest hands down.
That said, it's really more meaningful to compare the Cisco Professional certs - namely, CCNP, CCDP, CCIP, CCVP and CCSP - to the RHCE. You must first earn the CCNA, then you can go on to one or more of these mid-level credentials. Though the expense won't be as great as that for the RHCE, the amount of time and effort involved in earning a Cisco Professional cert is much more on a par with the RHCE.
I'd make the Red Hat/Cisco choice on the basis of where your current job (or future jobs of interest) might focus their efforts and energies, so that you should go one direction or the other based on where job opportunities and your interests lie.
This was first published in October 2005