What is Logicomix about? In 3 words: Godel, Escher, Bach. Of those 3 people, only the first appears in Logicomix, but like the Hofstadtler book by the same name, Logicomix is a comic book about the connections between the fundamental incompleteness of math (Godel), how we use paradox to understand that incompleteness (Escher), and how art reflects how humans can transcend logic (Bach).
On the surface, Logicomix is about the life of Brittish mathematician Bertrand Russell, drawn in a sophisticated and nuanced version of the art seen in Tintin. But really, is is trying to use a comic book story to convey deep ideas about the nature (limits) of logic/reason/mathematics and the nature of humanity.
In much the same way, Hofstadtler's Godel, Escher, Bach used stories about the Tortoise and Achilles to illustrate many of the same ideas for his textbook, and Stephenson uses pulp thriller fiction (using many of the same characters like Leibniz and Turing) to explore the same ideas.
The comic book format doesn't allow Doxiadis and Papadimitriou's Logicomix to explore the topic as deeply, but it may make it much more successful in reaching a larger audience.
In various ways, I have been reading about these ideas for a very long time, in theoretical computer science summer courses in middle school where we learned about the foundations of arithmatic and Cantor diagonolization, reading Marvin Gardner's Aha and Gotcha around the same time, thinking about the limits of utopia reading Huxley's Brave New World in high school, learning set theory freshman year, to learning about the limits of rational choice theory (e.g. reading Scott's Seeing Like a State) in grad school.
Unlike Stephenson's novels which pressuposes a lot of this background, Logicomix tries to address the ideas to someone who perhaps never liked math, and I think ultimately succeeds. For me personally it lacked some of the depth of say Asterios Polyp which used comics to explore the nature of art and humanity. But that may just be because I haven't really thought as much about art before, and thus I am probably the wrong audience for Logicomix.