As with just about everything, Lawrence Sterne's The Life and Opinions of Tristram Shandy, A Gentleman was one of, if not the first novel to incorporate illustrations.
Here are Tristram's illustrations of the plot arcs of the preceding volumes of his novel.
And here is an illustration of a gesture one of the characters made with his cane. The sentence below reads, "A thousand of my father's most subtle syllogisms could not have said more for celibacy."
After Sterne there is a gap (at least in my knowledge) of the use of intergrated illustration in fiction until the post-modern era. The short story writer Donald Barthelme wrote story collages.
He also included simple illustrations in at least one short story, Eugenie Grandet.
Perhaps the most famous use of simple line illustrations in a novel comes from Kurt Vonnegut's novel Breakfast of Champions.
The novelist W. B. Sebald often used photographs in his novels, a technique that was recently used by Aleksandar Hemon in his National Book Award Finalist novel, The Lazarus Project. The pictures below are from Sebald's novel Austerlitz.
Larsen distinguishes himself from these predecessors with the beauty of the illustrations. The authors discussed above were writers who used illustration to communicate very particular ideas in their works. Larsen is a very talented visual artist in his own right and so his illustrations carry a depth of substance the others don't. A collection of just the illustrations from the novel would still make a good art book.
The Selected Works of T.S. Spivet poses a number of challenges to the reader, but it does so in a way that's more obviously accessible than some of the other works I've mentioned. The charm of the narrator and the entertainment of the story could turn T.S. Spivet into a gateway book for people, showing readers they can be entertained and challenged by the same book.