A character named Darkel was scheduled to appear in the game, before being removed. He would have given Claude a number of missions that would have involved committing acts of terrorism. Contrary to popular belief, he wasn't cut because of 9/11, but some time prior because he didn't fit with the rest of the game. However, pictures of Darkel can still be found on the GTA III website, his voice actor (Bill Fiore) is still credited in the manual, and his missions were either deleted, converted into Rampages, or given by other bosses (El Burro's mission "I Scream, You Scream" being the most notable example).
Another character named Curtly is credited in the manual for the game, although nothing else is known about him apart from his intended voice actor (the late Curtis L. McClarin).
Fan Nickname: Due to being ordered around for the entire game, before his real name was revealed, Claude was referred to as "Fido". Also, Maria refers to Claude as "Fido" when he is ordered by Salvatore Leone to be her driver.
Killer App: For the PlayStation 2. Granted, the console had achieved the rare feat of utterly dominating the console market from the very day it was released, but this was the first game to truly show off the system's capabilities, and cemented it as the system to beat.
Shrug of God: Did Claude shoot Maria? "No one knows for sure what happened there" is the official line.
Too Soon: After 9/11, Rockstar North changed the paint jobs on the police cars so that they didn't resemble those of the NYPD. Some pedestrian dialogue was also changed and one mission that mentioned terrorism was removed. There was insufficient time between the disaster and publication for extensive alterations.
Urban Legend of Zelda: Some fans are completely sure that Claude was originally concieved as a speaking protagonist, because of a leftover sound from GTA 2 appearing in a trailer for the game. Rockstar denies that Claude was ever supposed to speak, though.
There were a ton of rumors about what content had been cut after 9/11, including a persistent one that Donald Love's last mission would have involved crashing a plane into a building, despite Word of God saying that there were never plans for large aircraft.
Another one was the Maibatsu Monstrosity being driveable.
And that Fernando Martinez was hidden somewhere in the game and had missions for you.