The book Nagato gives Kyon is Hyperion. It's a book/series about time travel, aliens, bizarre powers and things that may or not be gods/God... Hm...
More than that: After reading Hyperion, one may gain a whole new level of insight into what Yuki is and what her (and the Data Overmind's) motivations are.
In the second novel, they are described (Disproved in 4th book, Rise of Endymion) as made up of 3 factions. The Stables, who want to continue their relationship with humans. The Volatiles, who just want to kill all the humans. And the Ultimates, who just want to build their god, the Ultimate Intelligence. Guess who represents the first 2 factions soon after...
The scene in which Nagato gets impaled through the chest may be a Hyperion reference too.
In "Someday in the Rain", Kyon and Koizumi are playing a real TCG called Dragon All-Stars that features various anime/light novel characters; among the cards shown are "Lina and Naga" and a Gourry card.
In Dissociation, Yuki is reading Godel, Escher, Bach: an Eternal Golden Braid by Douglas Hofstadter. Yuki could start the trope on Suspiciously Apropos Literature.
Kyon notices that Time Traveller Mikuru has never been inside a fashion store — rapidly changing clothes on mannequins in the window of a fashion store are part of the Time Passes Montage made famous by HG Wells' The Time Machine.
Another Wells reference is made by Koizumi in the 9th novel, he says that Nagato can't catch a human virus, as she is a real alien, and not a "martian from the past."
The aforementioned episode is also a shout out to Star Blazers, which also took place on giant spaceships with giant cannons. The leader of the Computer club even quotes the Catch Phrase of Star Blazer's season 1 episodic villains by saying: "All hail the computer club!!!". The original line said by the villains every time they lost to the protagonists' crew being: "All hail the Gamilon Empire!!!"
In "Live Alive", Kyon says "Enjoy the festival. In a normal fashion." to Those Two Guys. This is a reference to Sousuke saying "Enjoy your bath. In a normal fashion." in Full Metal Panic? Fumoffu's onsen episode.
The name "John Smith" in itself is a direct reference to the British series Doctor Who, which is all about (you guessed it) time travel, sliding through alternate worlds and whatnot. Quite fitting for as alias for Kyon when it served as the alias for the Doctor as well.
Actually, John Smith is an extremely common alias used, just like John Doe is.
Also in Endless Eight, after being told about the endless recursion of time, Kyon utters something similar to Goemon's catchphrase from Lupin III. Also at one point, after Koizumi tells him to say "I love you" to Haruhi, he replies "Ore no turn!"
Yet again in Endless Eight, during the festival, Yuki buys herself an Ultraman mask.
In The Melancholy of Asahina Mikuru, from the 6th novel, Kyon referenced Veritaserum.
Compare Kyon's slow-mo fall through the window in Disappearance to Spike's in Cowboy Bebop.
In the episode "Remote Island Syndrome 2," the 'culprits' of the murder appear as black shadowed figures with slanted yellow eyes. This is also how unidentified criminals are portrayed in both the anime and manga of Detective Conan.
In each English book cover of the series, there is a little symbol on the top normally relating to what's going on in the book. In the sixth novel, the Wavering of Haruhi Suzumiya, the symbol just so happens to be the "Groundhog Day" Loop 's page image.
While explaining the concept of moe to Kyon, Haruhi holds up two manga anthology magazines as examples. One of them has Asa and Kaede of SHUFFLE!.
In "Remote Island Syndrome Part II" Haruhi imitates the sprites from the video game Ace Attorney, as well as the dramatic close-ups and, but of course, the "OBJECTION!". Itsuki runs with it and imitates Edgeworth.
Kyon seems to go with it, too: he's evidently playing the Mia to Haruhi's Phoenix, since he's mostly shown during the explanation with his arms crossed, which is one of Mia's default sprites (especially when channelled by Pearls), wears his collar open like Maya's and Pearls' costumes go when channelling Mia, and was the actual one who figured everything out, if his narration is anything to go on there. Like Mia, he also gets to add a little bit of the explanation to the reveal.
The fact that the "Groundhog Day" Loop episode contains a cicada-catching contest is also a Higurashi reference.
A more subtle reference is the pun of Yuki's name on Rei Ayanami. "Rei" can mean "cold" while "Yuki" can mean snow. Nagato and Ayanami were both Japanese warships that served in World War II.
At the beginning of "Live Alive", Kyon gets waylaid by two people dressed as Hard Gay and Akihiro Miwa.
In the final episode of Haruhi-chan, there's a Shout-Out to Disappearance, specifically in Yuki's Dating SimVisual Novel where Yuki gives the player character a Literature Club application form. The date in the upper left hand corner (intriguingly, Yuki used the Key Visual Arts date format in her game) was December 18, which is the date that Yuki hijacked Haruhi's powers and remade the world in the Disappearance of Haruhi Suzumiya.
A fairly unknown reference in the Western fanbase, an early episode has Kyon almost incomprehensively slurring a remark that roughly translates to, 'This has got to be a lie.' The reference is to an internet meme originating from Kamen Rider Blade where the main protagonist's slurred Japanese is referred to as 'Ondouru-Go' by the Japanese fanbase. In fact, Kyon's quote is copied exactly word for word from one of the more popular 'Ondouru-Go' phrases.
In the English dub of Melancholy (episode 3), during the second part of Yuki's initial exposition speech at her apartment about Haruhi and her being an alien an all that, you get this sequence:
Yuki: There is a reason she choose you rather than someone else.
The same shout out (no way/way) appears in chapter 30 of Dan Simmons' novel Endymion, between Endymion and the "ship" AI. Endymion is a sequel to Hyperion, which Yuki had just read and given to Kyon. It is reasonable to suppose Yuki was reading the sequel at the time and got the response there. There are neat parallels. Endymion/Kyon is protecting a girl (Aenea/Haruhi) with the fate of the world in her hands, and ( ship AI / Yuki ) are trying to protect both.