The game's first teaser trailer featured Harley Quinn in her costume from Batman: Arkham Asylum, though a completely new costume is seen in the final game. It is possible this trailer was made before a different costume was considered.
Contributed by Boyobmas
The Catwoman Episodes initially ended with her coming to Batman's aide, but late in development, the developers decided to give the player an alternate choice, allowing them to have the morally-grey Catwoman leave the city with her loot; the addition was implemented in two days.
Contributed by DrakeVagabond
The developers had considered adding a multiplayer element to the game, but ultimately decided against it.

According to Hill: "If we use all of the energy that is required to create multiplayer and instead focus this on the single player, would that deliver a better overall game?", and decided in the affirmative.

Multiplayer would later be a feature in Batman: Arkham Origins
Contributed by DrakeVagabond
Although the Robin seen in this game and Batman: Arkham Knight is Tim Drake, his "Animated Series" skin is of Dick Grayson as Robin.

Dick Grayson as Nightwing appears as a challenge mode-only DLC character.
Contributed by MightyKombat
Wearing Batman's "Animated Series" skin during the main story will result in Catwoman and Robin appearing in their respective Animated series skins as well. This also works for the "Harley Quinn's Revenge" DLC should the player exit out of it, continue from the main menu and select the Animated series outfit there.
Contributed by MightyKombat
Kevin Conroy, the iconic voice of Batman, described the game as "really, really dark." While relating the game's dark nature to the animated movie Batman Beyond: Return of the Joker, Conroy also said, "It involves a lot of the villains and it goes to that area "“ it's that dark."
Contributed by DrakeVagabond
The original idea was to take the game out of the asylum setting and onto the streets of Gotham City while retaining the level of design detail put into the asylum. Rather than a series of generic streets, the team wanted to include locations from the Batman mythos that were not only notable but meaningful to the character. Rocksteady was initially unsure how technical considerations would limit the scope of this idea.
Contributed by DrakeVagabond
The Detective Vision was redeveloped for Arkham City because it was considered to be too useful in Arkham Asylum, resulting in some players using it throughout almost the entire game; the visual effect also obscured the game's design aesthetic. One idea was to introduce a time limit on its use, but it was considered that Batman wouldn't make a gadget like that. Instead, it was designed to be difficult to use in certain situations.

The idea for a time limit on the Detective Vision would later be used in Batman: Arkham Knight.
Contributed by DrakeVagabond
The design team chose to have Batman start the game with access to the gadgets unlocked in Arkham Asylum, to convey the impression that Batman is fully prepared for the inevitability of things going wrong in Arkham City.
Contributed by DrakeVagabond
Rocksteady decided to not include the Batmobile, because it would be unable to travel on the city's broken terrain. Instead the team focused heavily on gliding as a sufficient means of transportation, and it was considered that putting Batman in any vehicle would make it a completely different game.

By the time they had programmed Batman to dive and glide between buildings of the asylum, the adaption of the gameplay to the city was considered natural.
Contributed by DrakeVagabond
Rocksteady decided early on that the Joker would die in the story, and developed the idea of him poisoning Batman with the same affliction, in order to show how the two diametrically opposed characters would interact in pursuit of a shared goal. Warner Bros. and writer Paul Dini did not oppose killing off the character as long as it was not done for shock value, and as long as they made it clear that Batman was not at fault, since he would not intentionally kill someone.
Contributed by DrakeVagabond
Batman's sidekick Robin also appears, featuring a shaved head and contemporary costume design that were intended to move away from his traditional "Boy Wonder" image.

Senior concept artist Kan Muftic explained:

"Our vision of Robin is the one of a troubled young individual that is calm and introverted at times, but very dangerous and aggressive if provoked. The shaved head is inspired by cage fighters, because we thought that Robin might be doing that in his spare time to keep him on his toes. Still, we kept all the classic trademarks of Robin's appearance, such as the red and yellow colors of his outfit, the cape and the mask."
Contributed by DrakeVagabond
In the Park Row district, in the alley around the back of Monarch Theater, the player can find a chalk outline in the shape of two dead bodies. This is the same place where Bruce Wayne's parents, Thomas and Martha Wayne, were killed by a mugger while the family were on their way home from the theater. This incident of course led Bruce to become Batman.

Around the outline, a bouquet of flowers and an interview tape from Hugo Strange can be found on one side, with said tape consisting of a single message from Strange taunting Bruce/Batman. On the other side of the outline is a single red rose. A button prompt triggers when near this rose allowing the player to pay their respects to the Waynes. Batman will kneel by the outline in silent contemplation.

Staying in this position for a minute will earn the player an achievement/trophy for paying respect to the Waynes.
Contributed by MightyKombat
Setting the date of the console or PC that the game is running on back to December 13th, 2004 (the day the game's developer, Rocksteady, was founded) and talking to Calender Man in the court house basement triggers special dialogue from him where he claims that "the end is near" and when it comes, he'll be there. This is likely a reference to the final game of the series, Batman: Arkham Knight, which was in development at the time, as well as it being the final entry in the Arkham game series.

This easter egg wasn't found by fans until 3 years after the game's release, when Rocksteady hinted at it's existence.
Contributed by Boyobmas
After the cutscene in which Spoiler:Wonder Tower explodes and Ra's stabs himself, his dead corpse can be seen hanging from the gate. After completing the story, his body will be gone and his sword will be left at the foot of the gate.
Contributed by DrakeVagabond
After the boss fight with Spoiler:Ra's, the player can either exit and continue the story or head back the way they originally entered. Heading back will lead to a dead end with a locked gate. Using a remote controlled batarang on the button its connected to, Killer Croc, a villain featured in Batman: Arkham Asylum, will burst though the wall and talk to Batman. This is the only time Killer Croc appears in the main game.
Contributed by DrakeVagabond
In the "Iceberg Lounge VIP Room" Challenge Map, Killer Croc can be seen sitting in the background smoking a cigar and having a drink. The Penguin can also be seen looking on.
Contributed by DrakeVagabond
During Protocol 10, the guardians of Wonder City will be stacked in a pile in the middle of Wonder Avenue. After Protocol 10, all guardians will be gone.
Contributed by DrakeVagabond
In "The Joker's Carnival" Challenge Map, reaching a 100 hit combo will cause the Joker to join the fight. He will have the same moves he has from the story mode and does not affect the score in the challenge.
Contributed by DrakeVagabond
Attachment
Throughout the city are a number of giant Cheshire Cat heads. There is also a giant yellow duck in the basement of the Steel Mill. These items may be in reference to Tim Burton's early Batman film, Batman Returns.
Contributed by DrakeVagabond
Attachment
In the Steel Mill, looking on the floor in Joker's Office next to Harley's old outfit, it's possible to find a positive pregnancy test. Spoiler:This is an allusion to Harley's pregnancy in the "Harley's Revenge" DLC.

In said DLC, however, Spoiler:, this would become nothing more than a red herring, as when the player re-enters the late Joker's office, Batman finds a baby's crib containing the puppet Scarface painted to look like Joker. Surrounding the crib are a number of used pregnancy test strips, all showing a negative result. Inside the crib is another box the tests came in, with the box warning that the tests can sometimes result in false positives.
Contributed by DrakeVagabond
Early in the game, Batman must locate the source of a sniper shot. The Joker reveals that the church the gun is found in is filled with explosives, but the tower will not explode immediately if the timer hits zero. Instead, the Joker will talk for a short period, hinting at key plot points from later in the game.

After his monologue, the Joker will warn the player that they "really ought to get out of there." If they do not leave, the bombs will indeed explode, leading to a Game Over.
Contributed by DrakeVagabond
At the end of Episode 3 of Catwoman's story in the Catwoman Bundle Pack, the player can choose to Spoiler:not save Batman, and leave Arkham city. The game will automatically rewind itself to the point before the choice was made. If this sequence is played backward, the Joker can be heard saying, "Thanks for the entertainment, Bats."
Contributed by DrakeVagabond
The Joker infects Batman with the TITAN disease by using his blood. This implies that the blood-type of Batman is AB+, or that The Joker's blood-type is O-. Either that, or they share the same blood-type.

This is implied by Batman not showing any signs of rejecting The Joker's blood. The Joker also has a plan to infect all of Gotham City with the TITAN disease by shipping his blood to the Blood Banks that supply the city. This would further imply that The Joker is actually a Universal Doner, otherwise everyone in Gotham with a non-matching blood type would die of Hyperacute Rejection.
Contributed by Tieresias
Attachment
During Protocol 10, the player can find a patch of fire shaped like a musical note on one of the Museum exterior's side walls. It's unknown if this was a coincidence or a joke put in by the developers.
Contributed by Boyobmas
Originally, Batman: Arkham Asylum was to be Mark Hamill's last performance as the Joker, as he wanted to leave on a 'high note'. However, after hearing that writer Paul Dini would return to write the sequel, and that Kevin Conroy would reprise his role as Batman, Hamill agreed to play the role one last time.

Spoiler:He would once more reprise the role for the hallucination scenes in Batman: Arkham Knight.
Contributed by KnowledgeBase
It is possible (with a glitch) to get over the walls of Arkham City. Doing so reveals a completely modeled Gotham, Arkham Asylum, and other areas not visible from inside the city's walls. As none of it is solid though, it must be explored on a single glide.
Contributed by Shadowmane
In the Wonder City Foundations is a shop called "Toys & Dolls". On the door is a sign that says "Gentlemen's Hats & Accessories", and a picture very similar to the Gentleman's Ghost face, a character in the DC Universe. In the window is also a toy "Ghost Train".
Contributed by brucewayne2814
Attachment
On top of a structure in the Industrial District near the Krank Co toy company building, the player can find Scarecrow's mask discarded on the ground. Scanning the mask is part of one of The Riddler's challenges.
Contributed by Boyobmas
Playing the Joker's Carnival Challenge Map as Robin will have The Joker express surprise that Robin "is still alive." Joker is confusing this game's Robin, Tim Drake (the 3rd Robin) for Jason Todd, the 2nd Robin that Joker killed in the comics. Spoiler:Jason Todd appears in Batman: Arkham Knight as the eponymous antagonist, with a reference to Joker torturing, brainwashing and seemingly killing him, making it more odd he'd confuse Tim with Jason.
Contributed by Funland47
Inside the Gotham City Police Department building is a list of recently arrested people. The names are: Joshua Dahdrai, David Tyndale, David Higgins, Jigar Patel, Noel Chamberlain, and Johnny Armstrong.

All of these people are actually developers of Rocksteady Studios.
Contributed by SRJ
Scattered all over Arkham City are newspaper clippings with the headline "Criminal Couple Gunned Down" and a smaller heading on the left that says "Boy Watches as Parents Die!". These are clear references to Prometheus, one of the famous villains in the DC universe, and a dark reflection of Batman.
Also, inside the old Gotham City Police Department building it's possible to find an Arkham Medical Examination Record for Prometheus, which states he "passed" and has been released on November 12th, 1982.
Contributed by SRJ
Inside the room where the Riddler's third hostage is imprisoned, the player can find canisters containing Scarecrow's fear toxin, used for a Riddler challenge in Arkham Asylum.
Contributed by SRJ
Attachment
During the first mission, when fighting off thugs in the alleyway as Bruce Wayne, the player can see Azrael watching the battle on a rooftop to the right. He will eventually throw down a smoke pellet and escape.
Contributed by SRJ
Using the Cryptographic Sequencer throughout the game, the player can find three hidden radio waves that transmit numbers.
These series of number can be deciphered with different mathematic methods, revealing a series of numbers, which need to be deciphered by correlating the numbers to letters of the alphabet.
Spoiler:These codes read out "I Will Return Batman", "You Will Pay For What You Have Done To Me", and "Fear Will Tear Gotham City To Shreds". The methods used to obtain these results, and their context, suggests that Scarecrow would return, which he would eventually do as the main antagonist of the 2015 game "Batman: Arkham Knight".
Contributed by Funland47
While fighting against The Joker, using Detective Mode's X-ray feature reveals that Joker has no bones. Spoiler:This actually foreshadows that he's really Clayface.
Contributed by ST3
In the Industrial Area is a lone boat off the coast of the city. Using the Cryptographic Sequencer, it's possible to open a highly secured trap door into the body of the boat. Spoiler:Inside the boat are a number of The Scarecrow's experiments, namely cockroaches. There is also a thug sitting in a chair, who will scream when approached.
Contributed by Funland47
Attachment
Whiling using the Cryptographic Sequencer, holding down all shoulder buttons while rotating the left analogue stick counter-clockwise and the right stick clockwise for around 5 seconds will make all characters have large heads. This works in both the standard game mode, and New Game+.
Contributed by Funland47