I am wondering if I'm just not smart enough to understand, but I've managed to slog through GEB and in the end the proof seems contrived, it stands on self reference.

Nagel & Newman is much better if you find GEB a slog (which was also my experience). However, Gödel’s theorem is fundamentally due to self reference. But so is the fact that the power set of countable infinity is uncountable, in a similar way.