In The Lord of the Rings, Legolas and Gimli are very much Those Two Guys, especially in relation to Aragorn. Merry and Pippin also qualify. Though less in The Return of the King, where they are separated and get bigger roles as knights of Rohan and Gondor respectively.
Nobby Nobbs and Fred Colon frequently fulfill this role in City Watch stories.
Their various international counterparts as every locale has an ethnic equivalent of Fred & Nobby. Lampshaded in Jingo.
Inspectors Lestrade and Gregson in Sherlock Holmes. Good enough coppers in their own way but naturally can't compare with the Great Detective, but only in the debut novel, A Study in Scarlet. They never appear together after that, with Gregson largely fading into the background, while Lestrade attains enough prominence to get his own trope.
In the very long 18th century Chinese novel The Story Of The Stone, written by Cao Xueqin and Gao E, There are two minor characters who appear in the first two chapters. They are Jia Yu-cun, a tutor, and Leng Zi-xing, an antique dealer. They have a conversation over wine in a tavern, and the point of this conversation is to give a description of the Jia family and their situation to the reader.
Ivanhoe opens on two Anglo-Saxons: Gurth, a swineherd, and Wamba, a jester. They playfully banter, making a linguistic observation in the style of Steven Wright. Wamba misdirects the local man of the cloth and a Knight Templar away from the home of Cedric, the local thane, in order to protect Cedric's ward from unwanted advances. (They make it to the hall anyway, making for an uncomfortable dinner.) While it would be an exaggeration to call those two main characters, they do get more characterization and some plot-relevant moments later in the book; Wamba even manages to free his master Cedric from his jail cell in their enemies' castle virtually all by himself, by the simple expedient of a clever disguise.
Bodger and Grift in JV Jones' Book of Words books are pretty much used for Rosencrantz-and-Guildenstern observational purposes for the whole trilogy, and occasionally have to do something important for the plot.
Givenar and Antinas in Space Marine Battles, who can't stop bickering and joking, to Lysander's neverending annoyance.
The The House of Night series has a female version in 'the Twins', two of Zoey Redbird's friends, who aren't literal twins (in fact, one is the Token Ethnic Minority) but are very close friends to each other. They even have complementaryElemental Powers, with one being fire and the other one water. I can't even remember which has fire and which has water. They have a brief romantic fling with a more typical set of Those Two Guys, incidentally.
Of Mice and Men has a set as the main characters. In any other book, George and Lennie would be Those Two Guys, and Slim would be The Hero.
Don Quixote: Pedro Pérez, the curate, and Maese Nicholas, the barber. Better known as "The curate and the barber", two guys from the same town as Don Quixote, who are fond of chivalry books, like Don Quixote. Unlike Don Quixote, they are completely ordinary (sane), and... well, you would not find any other personality trait in them. His personalities are exactly the same, their names are too simple to stand out ("Pedro Pérez" is the Spanish equivalent to "John Smith"), In the first part, they have a significant involvement with the plot, but in the second part, they only appear in the beginning and in the end of the novel (with only a mention of the curate in one intermediate chapter).
Opera managers Richard and Moncharmin in The Phantom of the Opera. This trope continues into the stage show with these two (in which their names are changed to Andre and Firmin). There isn't even consistency in casting; sometimes Andre is the short one, sometimes it's Firmin. Often an actor will play both roles during their run with the show, being cast as one essentially means you can play the other just as well. Apparently the only person who can tell them apart is the Opera Ghost who addresses their notes accordingly.
In a way, Tomo and Walberg of George R.R. Martin's Thousand Worlds, a pair of adventurers who visited many planets. They are almost always mentioned together when someone brings them up, and they are Memetic Badasses in-universe. Unfortunately they have yet to actually appear in a story.
Bella's friends Mike, Jessica, Angela, and Eric in Twilight. Also the members of the wolfpack who aren't Jacob, Sam, Leah, and Seth.
The main characters of The Other Guys are what happens when Those Two Guys manage to become the heroes after the actual heroes die.
The novel Wives and Daughters has Those Two Women. The Misses Brownings, Miss Browning and Miss Phoebe are family friends of Mr. Gibson and his daughter Molly. They are fairly similar characters and always paired together. Lady Harriet even calls them Pecksy and Flapsy.
Dick and Dolly in Little Men, then Stuffy and Dolly in Jo's Boys.
Mr. Hall and Mr. White play this role to Doug in Parellity.
Donegan Bane and Gracious O'Callahan, the MonsterHunters, in Derek Landy's The Maleficent Seven, qualify as they are primarily used for comic relief. While shown to be very talented fighters, they never take centre stage except for the purposes of comedy.
The Knight Life series has Buddy and Elvis, two drugged-out muggers who end up working for King Arthur's campaign and become jesters of a sort for him after witnessing him receive Excalibur ("the day-glo sword") from the Lady of the Lake.
Dave Barry's Only Travel Guide You'll Ever Need claims that Liechtenstein and Luxembourg are not countries at all but "minor characters in William Shakespeare's famous play Hamlet II: The Next Day."
The Malazan Book of the Fallen has these characters in spades. Bromances are common and almost every two-man pairing has shades of this:
Kharkanas Trilogy note Forge of Darkness, Fall of Light, Walk in Shadow
Prazek and Dathenar
Other books in the series:
Kalam and Quick Ben
Fiddler and Hedge
Shadowthrone and Cotillion
Tehol and Bugg
Stormy and Gesler
Bauchelain and Korbal
Toll the Hounds:
Scorch and Leff. Never seen without each other, they hang around in the background of Torvald Nom's story arc and are his only subordinates when he becomes captain of Lady Varada's house guard, but otherwise have little significance beside being comic relief. They also act as one entity throughout the book.
Lazan Door and Madrun Badrun. The former is tall, almost skeletal, and bald, while the other is broad-shouldered, short-legged and shaggy-haired. One wears a whispy cloak, the other is clothed like a court-jester. They are always together, and appear to be Studious Lock's accomplices. They also serve as a sinister contrast to Scorch and Leff's comic relief.
Craig and Fry, the two employees assigned by the American insurance company as bodyguards to watch over Kin-Fo in Jules Verne's Tribulations of a Chinaman in China. Inseparable and largely indistinguishable (they are cousins), they appear like spiritual ancestors of the Thom(p)sons, if a bit more competent.