The writeup above shows that under every
compression scheme, you get strings that do not compress and some that do.
Random data doesn't compress well because compression algorithms reduce redundancy in data. In Information Theory terms, the compressed output has a higher entropy than the input. However, random data has maximum entropy (or close to the maximum) and so cannot be increased.
That is, 1000 bits of random data might have an entropy of 999 bits, while normal text might have 400 bits (that is, considering characters' frequencies). Huffman would compress the text to little more than 400 bits, while the random data would get around 1000 bits (depending on the distribution of the characters).
Considering the extra file size required to decompress the file is not that important, because as the original file size grows, it will become more and more insignificant.
Anyway, it would be interesting to discuss what is random. For example, suppose we encode text with 7-bit ascii, and we interpret that data in chunks of 8 bits. Usually, it would appear to be random data, and it would not compress much using Huffman encoding. But it is very likely that Huffman encoding considering 7 bits at a time would compress it.
Therefore, randomness in data is a subjective concept, that is, it is random relative to some supposed organization.