Yeah I always thought that the construction of Gödel numbers was always the weakest part of the proof / the biggest leap of faith / the part your prof would just hand-wave as being a valid move.

Of course once you get into Turing machines it all flows more naturally, what with all of us being accustomed to "code is just data".