It appears to me that what Tegmark specifically proposes is not readily intelligible, see How can the physical world be an abstract mathematical structure? Even if we make it more intelligible by adjoining a God-like entity that animates symbology into reality Gödel's incompleteness is essentially inconsequential for Tegmark because he is a physical Platonist. I.e. for him mathematical truths about reality exist out there regardless of whether or not our first order languages happen to be adequate for proving them. At best, one can get a compatibilist account of free will out of it, where, although everything is mathematically predetermined, some things are transparently so, because they are "provable" in our theories, and others are only transcendentally so in the Platonic sense.
But, as our formal capabilities develop, the latter may move into the former column, after all, the original Gödel sentences become provable when the original theory is strengthened. So as we advance we are destined to find out more and more how what seemed "free" before was in fact a mathematical necessity. But this is a common theme of compatibilism whether or not incompleteness is invoked to back it up.
The most famous attempt to apply Gödel's incompleteness ideas to explaining puzzles of conscious mind are Hofstadter's classic Gödel, Escher, Bach, and its sequel I Am a Strange Loop. The added bonus is that Hofstadter discusses in detail the incompleteness based arguments of Gödel, Lucas and others for human creativity making a qualitative difference between the man and the machine. Here is Lucas:
"However complicated a machine we construct, it will, if it is a machine, correspond to a formal system, which in tum will be liable to the Gödel procedure for finding a formula unprovable-in-that-system. This formula the machine will be unable to produce as being true, although a mind can see it is true... In a sense, just because the mind has the last word, it can always pick a hole in any formal system presented to it as a model of its own workings. The mechanical model must be, in some sense, finite and definite: and then the mind can always go one better".
Alas, this argument is overly optimistic about mind's capabilities. According to Hofstadter himself, it is self-reference ("loop") inherent in Gödel's construction that allows computing and processing to imbue itself with meaning and understanding, and therefore "create" consciousness and "I". Martin Gardner writes in his review of I Am a Strange Loop:
"Consciousness for Hofstadter is an illusion, along with free will, although both are unavoidable, powerful mirages. We feel as if a self is hiding inside our skull, but it is an illusion made up of millions of little loops. In a footnote on page 374 he likens the soul to a “swarm of colored butterflies fluttering in an orchard.” Like his friend Dennet, who wrote a book brazenly titled Consciousness Explained, Hofstadter believes that he too has explained it. Alas, like Dennet, he has merely described it".
Martin Gardner unlike Tegmark, was a mathematical Platonist rather than a physical one, i.e. he believed that mathematical objects objectively exist out there, but not that the universe is made of them.
There is a fatal flaw with applying Gödel's, or any other mathematical theorem, to philosophy. One has to assume that conditions of the theorem are met in reality, so any consequences a theorem can provide are already baked into the original assumption, and can be painlessly rejected along with it by those who dislike them. I think Wittgenstein had something like that in mind when he said that Gödel's theorem has no philosophical consequences, see Matthíasson's Interpretations of Wittgensteins Remarks on Gödel.