What certification better compliments the MCSE: CCNA or RHCE?

Thanks for your inquiry. Though you don't say, I assume you're working on a Windows 2003 MCSE; if it's Windows 2000 and you're more than half-way done, finish up then take the 70-292 and 70-296 upgrade exams as soon thereafter as you can (if you're less than halfway through Win2000 MCSE, it's probably best to drop that course of study and switch to the Windows 2003 exams instead).

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.