Science fiction which only recycles the surface trappings of the genre without using them as a vehicle - i.e., that doesn't take advantage of the freedom allowed by world-creation to get at something - is a hollow failure. Using a novel to investigate the function of language itself, as this one does, seems an abstract and sterile endeavor and in lesser hands probably would be, and might be impossible if you couldn't invent a counterfactual world that better exposes the uneasy conflicts inherent in such a question. Gene Wolfe's New Sunnovels are about the limitations of language - the Ascians who can only speak in stock phrases and communicate meaning by how out-of-tune the uttered phrase is with the current situation; or the degeneration of imagination as moves from direct experience to more and more iterations of mere telling, like people breeding in a prison who thought bees were a foot across because they'd only heard about but never seen them; or the silo-ing of genres into guilds. Gun, With Occasional Music is a meditation on language using the medium of detective fiction, and properly using the freedom that science fiction allows to explore its core concerns - language's richness and its relationship to truth, authority, and action.
As a point of comparison, the influence of Philip K. Dick on this novel is obvious, in the same way that Black Sabbath's influence on Metallica is obvious - Lethem takes what's good about PKD and makes it better, with much better writing. Gun is Do Androids Dream of Electric Sheep, more fully developed and better-written. Androids is a manatee and Gun is a dolphin. If you need this novel put in terms of other novels, it's about half Androids, a quarter Scanner Darkly, and a quarter auster's City of Glass, the latter of which is the only work of anti- or meta-detective fiction I've read that does that particular "genre" justice. (Again, by properly using it, and not leaving the genre's tricks un-fired on the mantelpiece.)
At its core, this is a detective novel about a half-washed-up private eye trying to get a guy off for a crime he didn't commit. It's the world that they inhabit The plot really serves only as a medium for you to notice the author's investigations of language, and if the book has a flaw, it's that the plot is overly complicated and distracts from the central value of the novel. The world this detective finds himself in is one where questions are illegal, metaphors are misunderstood, jokes are taken literally, and by the end, even too many simple statements become suspect. There are also evolved animals and developmentally-accelerated children, though (key to my criticism here) none of this is really essential to the plot. There is a recognition of class, though this seems more a necessary part of a detective novel, and less an actual exploration. In a nutshell, the animals and babyheads (more on them below) are clearly lower class. So?
Questions are an obvious threat to authority ("The number one enemy of progress is questions!" - Jello Biafra) and in this world there is an Inquisitors Office, which contains the only people allowed to ask questions, and then only in the course of their investigations (them, and the occasional private investigator - but they need a license to ask.) There are several references to psychoanalysts - the most instrusive question-askers of all - but they're illegal, replaced by Inquisitors. In fact the only psychoanalysts encountered in the novel are a hollowed-out degenerate incarnation thereof, going door-to-door like Jehovah's Witnesses, and they're evangelizing - that is, telling, not asking.
But the threat from language to authority comes not just from questions, but from metaphor. Dictatorships are famous for their difficulty understanding, and (therefore) their intolerance of, parody and ambiguity. Consequently this is a world where authorities either cannot understand metaphors, or have forced them to become literal. Criminals are put in actual freezers. Everyone is using an officially issued drug ("make") and one of them is described thusly: "Think of it as the opposite of deja vu - nothing reminds you of anything, not even of itself." A more certain death for metaphor could not be described! Evolved animals jump from figures of speech into real life - Metcalf has a monkey on his back at one point, a sheep is afraid to disobey the man she lives with, and just as he was emasculated in leaving the Inquisitors Office to become merely a "private dick", his manhood was taken by the woman who broke his heart and left him after what he thought was a temporary trade in genital sensation, made possible by future neuro-programming. The character who turns out to be his arch-nemesis is an evolved kangaroo. This one I couldn't process other than to realize that since Joey is common young gangster name, it would make sense in this world for that gangster to be an actual young kangaroo. Every now and then the prose snaps out of gumshoe-rhythm but it's typically associated with certain characters; Testafer is the closest Lethem comes to exposition, and to a lesser extent the antagonist Phoneblum. But these sections don't expose the central theme, and the closest Lethem comes to just giving away the come occurs when the protagonist, in frustration with the babyheads, asks "What if I told you I thought Truth and Justice were two completely different things?" This narrator seems to actually think in clever metaphors (as is common in detective fiction) but the Inquisitors Office goons often flatly don't understand his constant wordplay. Late in the book, when the character wakes after six years in the freezer to an even worse world, people don't even understand jokes without the help of computers they carry with them to tell them they just heard a joke. (They still don't understand the jokes, but they know the appropriate response is to laugh.) TV shows and even the news are abstract and non-representative. The news is delivered with music, which, as an abstract art-form, is un-threateningly indirect and un-revelatory (This is how the USSR announced Premier Konstantin Chernyenko's death, though it's certainly not the only dictatorship which has been less than eager to explicitly communicate bad news.) But even TV shows are abstract in this world, seemingly serving as animated Kandinsky paintings, like visual muzak.
Then there are the babyheads, the accelerated infants, deliberately drawn as the most disturbing and creepy entity in the novel. There's an implication that the babyheads are the future, spouting pseudo-profound nonsense (which is therefore harmless); I can't help but think he's picking on the post-modernists here. In the babyhead bar, they make clear their contempt for the prohibition on question-asking, but you don't get a feeling of liberation that you're in some inner sanctum where linguistic freedom has been protected. Rather, you're clearly in a cognitive and linguistic ghetto.
A final thought on the predictions that Lethem got right. Everyone in this world has "karma", a system of points which, when the Inquisitor's Office has penalized you so much it reaches zero, you're shipped off to the literal freezer. Reading this in 2019, you can't help but think of China's social credit system, which is amazingly under-discussed in the West. There is no discussion of how the world got to be this way - it's not really what the novel is about - but as the fire chief described in Bradbury's Fahrenheit 451, I can imagine a populist uprising driven by grass roots intolerance of question-askers in an increasingly complicated and difficult to negotiate world. There's no mention of a top-down central state here.
At the time of its publication the term "slipstream" was thrown around a lot as a category for this book, equal parts science fiction, litfic and post-modernism. But like most attempts at artistic hybridization, it looks more like one than the other, and Lethem falls more on the literary side. The critical question: is the novel about the technology? That is, do you and the writer care about the details of how things work, or are they a literary conceit that's serving another narrative purpose? This is why this novel, Fahrenheit 451, and Star Wars are not really science fiction. They create a setting that serves a purpose in the themes they're exploring, but Lethem and the reader do not care how the babyhead technology works (same for a light saber or the mechanical hound.) For that matter, in modern writing and film, many other genres have incorporated the superficial trappers of science fiction - thrillers especially, but increasingly romance as well. Another example is John Updike's not-really-successful science fiction experiment Toward the End of Time. It's literary fiction (fair enough) with some genuinely interesting science fiction ideas, unfortunately shoe-horned in. Updike wasn't fooling anybody with how he usually writes.
If I have a complaint, it's that the first few pages I was put off by the annoying intensity of the detective novel style. It's far beyond what would be needed to tell us this is a detective novel, and I appreciate that a debut author wants to showboat a little in terms of demonstrating his master of the idiom - although, for example, David Mitchell manages this better and less self-consciously in Cloud Atlas.