It does get worse in the sense that there could be languages whose description is incompressible (we can simulate this, assuming hash functions approximate random oracles, by saying "choose a secret key; now the language is 'every string whose HMAC value under that secret key is even'").

If you accept some axiomatic assumptions about infinite sets (that are common in mathematics; I'm not sure exactly what the weakest required axiom is for this), then you can even believe that there are infinite languages that have no finite description at all, very much akin to the commonplace claim that there are real numbers that have no finite description at all. There are formulations of mathematics in which this is not true, but most mathematicians seemingly work in formulations in which it is true.

I even expect that we can probably prove this directly using the powerset operation and diagonalization, which doesn't require particularly strong assumptions about infinities.