I wouldn't bother, it is an incomprehensible mess, impossible to get through, pretentious, non rigurous sloppy thinking, and ultimately a disservice to Godels incompleteness theorem.
As having taken undergrad/grad courses in logic and set theory, any interesting nuggets about recursion/completeness/incompleteness/etc that one could glean from GEB can much more coherently and succinctly be obtained from a proper book on logic/computability.
The counterargument would be that this book is meant as entertainment: from my experience with the first ~200 pages, it was a complete chore to read, as ideas were presented enigmatically and slowly, to the point of frustration. Granted, my attempt at reading it was almost a decade ago.
Do you have any suggestions where to start? Are there perhaps online 'starter kits' that would guide me through what courses/books/whatever to work through? I find that one of the most difficult parts of self-learning: there's often no clear syllabus available.
Why not, for example, see it from Hinton's philosophical point of view (besides that the papers are very boring and dry, of course)? He made a very good defense against Pylyshin and Fodor and a few critiques of Hofstadter _and_ the algorithms are shipping on Google Search and things like that.
I don't know if I'd have the patience to read it today.