The complexity I'm referring to is the complexity of the AGI code i.e. the length + log-running time of a hypothetical program producing the AGI code.

Or suppose we're looking at the complexity of programs that find an AGI program. Presumably high, right? Except that the finder can bypass the time cost by pushing the search into the returned AGI's bootstrap code.

This wouldn't quite work since the "AGI" would then be penalized by very long bootstrap. Since the measure of intelligence takes resource constraints into account such an "AGI" wouldn't be very intelligent: it wouldn't count as an actual AGI.