Two things make the book. The first is the fascinating character of the narrator, whose hard-boiled but occasionally lyrical voice becomes familiar (perhaps too familiar) in later Zelazny but must have been fresh in 1965. His past as a former fighter against the alien Vegans and quisling humans who have taken over the devastated earth, combined with his present as a chief administrator collaborating (at least superficially) with the administrationn makes us never quite sure what he is up to himself but eager to find out. He is a hero who is trying to keep his heroic identity under wraps. He does things like dismantling the Great Pyramid for laughs. And there are the little touches like dropping in on his friend's daughter's seventh birthday party.
The other thing is just the writing: first, the setting up and description of the bizarre blasted landscapes of the future Greece, the voodoo celebration in Haiti, the shift in perspective as he fights the golem, the Athens hotel room covered with plaques commemorating Conrad's life as Konstantin ("I was really afraid to go into the bathroom"). And second, of course, the humour - the skill Zelazny had in combining the contrasting styles of demotic with epic and making it funny rather than just cheap.
The book is not without flaws. The plot (both the sequence of events in the story, and the conspiracy among several of the characters) has a lot of holes in it. Conrad appears to have married Cassandra without telling her how old he is; she in her turn surprisingly survives apparent death and then doesn't contact him for weeks, showing up just in the nick of time to save them all from the Black Beast of Thessaly. (No apologies for spoilers - the book has been a classic for forty years.) The invisibilty of Conrad's immortality to the administrative system is rather less credibly established than that of the protagonist of Zelazny's later My Name Is Legion.
But I loved rereading it, and am wondering if I might make the complete works of Zelazny into one of my future reading projects. (I should add that I got the idea of setting myself reading projects in the first place after discovering from a biography that Zelazny planned his own leisure reading fairly meticulously.)