EAL4...so what (Score 5, Informative)

The CC evaluation comes in two parts:
A profile for the evaluation, and the assurance level to which you achieve that profile.

So if your profile is essentially "can boot" you can probably achieve that with a high level of confidence. All this talk of EAL4 is pointless unless you are told what the profile is.

In the best case, this only means that RH (and Windows, for that matter) could be used in a system carrying information classified at a single level, say, "secret".

In no (normal) circumstance would either RH or Windows be used to handle information classified at two different levels, such as secret and unclassified. If you want to do that, you need to use Trusted Solaris or some other evaluated "Trusted" operating system. Getting a evaluation for a system that can label information and keep different types of information apart (B1 or B2 in DOD Orange Book parlance) is a whole different ball of wax than what RH and Windows received (C2).