The concept of this episode is a play on the idea of the Lost City of Atlantis; the title is a reference to "the Deep South", a term used to describe parts of the Southern United States, and the fact that Atlantis and Atlanta sound similar is used throughout the episode.
Zoidberg runs from danger twice like Curly Howard of the Three Stooges, especially with the dialogue "whoop-whoop-whoop-whoop-whoop-nyuk-nyuk-nyuk!!!". This is not the only case as Zoidberg runs away gibbering "Whoop-whoop-whoop-whoop" in several episodes, which is one of the several references to the Three Stooges on Futurama.
The unbreakable diamond filament is a reference to Arthur C. Clarke's The Fountains of Paradise, where diamond is used as a building material for a space elevator. The tether that holds the filament would play a role in a later episode.
When the camera zooms in on Fry and Bender's bunks before Fry first talks to Umbriel, we see several things propped up against the wall. In the lower right corner is a Rebel Alliance fighter helmet from Star Wars, the same helmet he wore during "When Aliens Attack", a banner from Mars University and also the sword Bender stole in the earlier episode "A Bicyclops Built for Two".
Umbriel's name is a reference to Ariel, the main character in Disney's animated motion picture The Little Mermaid. Ariel and Umbriel are both moons orbiting Uranus, named for two of the sylphs in Alexander Pope's The Rape of the Lock.
Umbriel's father, "The Colonel", parodies the animated version of Colonel Sanders seen in contemporary KFC commercials.
Extremely funny sight gag: Fishing in mid-ocean, Leela pulls up . . . a boot. Casting again, she hooks something and exclaims, "This feels twenty times as heavy!" She pulls up . . . a box marked, "Boots: ten pair."
There is a reference to the 1972 film Deliverance when Bender nervously hums the opening notes to "Dueling Banjos" upon arriving in Atlanta.
The song Atlantis by episode guest star Donovan is played early in the episode during the montage sequence of Fry and Umbriel's date; and the later narration of the history of Atlanta is a parody of this song.
In the story of Atlanta a Ted Turner statue is shown being mounted above a SeaNN sign, a parody of CNN. The weight of the statue is the last straw, and causes Atlanta to sink into the ocean.
The concept of mermaids not having the same reproductive functions as humans is a reference to the mermaid problem. When Fry wishes that Umbriel could've been a mermaid with "the fish part on top and the lady part on the bottom", this is a jab at an episode of Night Gallery called "Lindermann's Catch", about a fisherman who wants to give a mermaid he's fallen in love with legs, but his wish backfires when her human half (her head) also becomes the fish part. It also parallels the Red Dwarf episode "Better Than Life", where the Cat claims that conventional mermaids are built "the stupid way around", and reveals his mermaid girlfriend Miranda who has a torso resembling a giant fish and a pair of human legs (and presumably the reproductive organs associated with them). It also parallels a surrealist painting by Rene Magritte which depicts a mermaid with a fish torso and a woman's legs which has washed up on shore. There is also an episode in a Russian cartoon "Charles Darwin - Origin of Species" where a magician makes a women first transfer into a fish and then backwards and then saws the woman apart, "connects" her again and then a normal mermaid and one with the fish torso and human legs, behind and reproductive organs come out.
Umbriel and Fry watch a whale and a giant squid wrestle, a reference to the Squid and Sperm Whale panoramic at the American Museum of Natural History and also exactly resembling the Apollo 18 album cover by the band They Might Be Giants. In an interesting side note, The Drinky Crow Show pilot was about nobody believing he saw a mermaid; Billy West (Fry among others) voicing Drinky Crow and They Might Be Giants doing the theme tune to the show.
There is a Krispy Kreme outlet in the lost city, a reference to Krispy Kreme's popularity in the South. However, unlike Coca-Cola, CNN, and other Atlanta-centric jokes seen in this episode, Krispy Kreme is not based in Atlanta. It is based in Winston-Salem, North Carolina.
While underwater, Bender is seen reading The Atlantic Monthly.
Bender's announcement that "in the event of an emergency, my ass can be used as a flotation device" is a reference to the movie Star Trek: Insurrection, in which Data says "in the event of a water landing, I have been designed to serve as a flotation device" upon resurfacing in a lake.
After Fry announces his intentions to stay underwater with Umbriel, Zoidberg invites him to come and visit his little house outside of town but "The Colonel" shakes his head and Fry says that he can't because he is trying to join the country club. This is a reference to the anti-Semitism that once ran rampant across the world, but strong in the Deep South until the early 1960s. This is one of many references to Zoidberg's Jewish-inspired origins, which is itself a joke because he is a shellfish, a non-kosher food that Jews are forbidden to eat under dietary laws (Kashrut).
"The Colonel" suggests Umbriel date a dugong, a sea creature believed to have given rise to the legend of mermaids, from Macon, another city in Georgia
In "The Simpsons" episode "The Trouble with Trillions" caffiene evolving aquatic life is referenced in this episode.