Computers are not truly random unless you spend some money to buy a hardware random number generator. These typically utilize actual measurements of a physical process that is truly random, like radioactive decay or the static from radio frequency receivers.
Flipping a coin is far more random than a computer's algorithmic random number generator (which are usually called "pseudo-random" because they are not truly random).
The problem with the RNG that Civ uses is that it is one of the worst types of RNG algorithms in common use. It is in the Linear Congruential family. It somewhat better than it could be because it is only using the high order 16 bits rather than all 32 bits. The full 32 bit integer generated using the method that it uses has the fine property of alternating between even and odd - if you get an even number, the next number is always odd (and vice versa). This is because the low order bit (the one representing the 1 position) alternates between 0 and 1. As I recall, the 2nd lowest order bit (representing the 2 position in the binary number) uses a patter than is "0011". They get more complex after that, but each bit in the binary number does follow its own completely regular pattern. Where each bit starts in its own sequence depends on the seed that is used. Throwing out the 16 low order bits makes the patterns harder to recognize (and more complex with longer periods). Another interesting property of the type of RNG is that if you take the numbers in the order they are generated and use each group of 3 as a set of x, y, z coordinates you find that all the numbers fall onto a set of planes (in this case it is not more than 16 since the number of planes does not exceed the number of bits in the output, and it is typically lower).
I would have gone with the Mersenne Twister myself (it is a a modified Twisted Generalized Feedback Shift Register Sequence (TGFSRS) type generator), or perhaps the SIMD-oriented variation (to take advantage of those parallel processing instructions on every CPU in PCs these days - although this version was not available when Civ4 was released, it may have been when BtS came out). It is, for most purposes, one of the best algorithm available. Given the amount of memory used by Civ4, the extra 2 kilobytes (or something like that) of memory that it would use is trivial. The random() function that comes with the Python that Civ4 comes with uses the MT algorithm.
Which brings me to an actual point. You don't have to "test combat odds". The combat is controlled by the software. You have the source code for the software. You can, therefore, just look at the program and see how it does what it does. If it alters the outcome for the player depending on any factor, like the current score, then code that does that will be present in the source code. If there is no such code, then it doesn't do that. No "looks like" or "seems like" or "its close", just "it does this" or "it doesn't do this".
To the same precision it goes up drastically as you pointed out.
