That’s a rather tough question to answer. Cisco, Microsoft and Redhat certifications all are well recognized in the IT job market and will certainly help your career should you obtain them. Question is how much time and money do you have to invest in certification and ultimatley where would you like to eventually end up?
My advice for a quick path into the job market would be to seek some type of administration cert. If you choose Microsoft’s route, the MCSA cert is a good start. It is a recognized cert in the job market and will land you a better paying job out of the gate then the CCNA would. A nice thing also is that an MCSA cert can be upgraded to MCSE status with two additional tests. Specializing in security is also a good choice since security is such a hot topic these days.
Once you have your foot in the door, then expand to the CCNA and maybe even CCNP. These certs coupled with the experience you would now have as an administrator will expand your value in the job market greatly.
I’m affraid my knowledge of Redhat certs is limited at best, but if the job market in your area dictates Redhat to be a better career path, then my advice would be to seek the Redhat equivilent to the MCSA and follow the same path as above.