1) An estimate of complexity is what it is - an estimate of complexity. It's not a claim that the way to achieve AI is to figure out the details of the particular encoding that nature ended up using, so the precise nature of those rules is not something we care about.

2) While it's true that those runtime rules (which we can kind of consider as the "interpreter" for our DNA) are extremely complex, this has almost zero bearing on the informational content in our DNA that is put towards creating the "intelligence algorithm", whatever that is. Sure, there's probably a bit of extra compression based on the fact that the physics allows some actions to be "built in", but unless you believe that DNA is physically optimized to make intelligent computer construction very concise, the logical content of these computations is probably explicitly "written" in.

And it's hard to believe that DNA is somehow specifically optimized for intelligence, because it was first used in completely unintelligent creatures and appears in exactly the same form now.

Now, it may be the case that DNA's physics are tailor-made to efficiently code for useful physical structures. But intelligence is a level of abstraction above that, and we're all but guaranteed that very little compressibility exists in the "language" for such higher level constructs.

What would an argument be without a strained analogy: if you're writing a complex web application, the size of your application is roughly independent (within an order of magnitude, for sure) of the architecture that it will ultimately run on (where by "size of application" I mean the size of everything that it takes to run it, interpreters, frameworks, etc.). Sure, the binary size might be slightly different depending on whether you're writing it for ARM, PPC, x86, etc., but not hugely different.

We would be extremely surprised if on three platforms your executable weighed in at 10 mb and on a fourth (which had a few different machine level instructions) it compiled down to 10 kb - the only way we could imagine that happening is if someone somehow "cheated" and embedded large parts of your actual application logic into the processor, adding specialized Ruby on Rails instructions to the machine code, or something like that. :)

Encoding and dynamics details may make differences in compressibility, but past an order of magnitude, you're really talking about "cheating", and it's an Occam's Razor problem to assume that nature optimized in such a way for intelligence...