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.

I think you certainly grasp the gist of things if you understand that the point is self-reference. What makes the proof shocking and beautiful (at least, IMO), is how sparse a toolbox Gödel is working with (and, perhaps, how clever the construction is). Contradictory self-reference in, say, plain English or naïve set theory, is not particularly surprising (at least to our modern eyes), because those are rich languages where you can express an extremely wide range of statements, but Gödel manages to smuggle it in using just whole-number arithmetic and first-order logical statements, which provides a recipe for doing so in essentially any formalized system of interest to "normal" mathematicians.

Some comments elsewhere in this topic mention that you can use the halting problem to arrive at the same essential conclusion in a more understandable way (and certainly one less fraught with small technicalities to work through), but (again, IMO) there's a certain mischievous magic to the way the Gödel sentence gets constructed that makes it very fun to work through for the first time.