Deleted Scene: One of them has two guards who screwed up and allowed Maximus to escape about to be executed with arrows, and Commodus walking in front of them while the archers are tensed to fire, and standing directly between the two condemned men as they are killed by arrows. This is supposed to show how self-destructive he's become since becoming emperor. This scene and several others have since been added back in with a recent Director's Cut, as is the increasing norm for a Ridley Scott movie.
Originally, Maximus was supposed to fight Proximo in the Colliseum after being captured, probably as a penultimate Kick the Dog from Commodus.
Nick Cave was asked to pen a sequel. It featured poor Maximus being reincarnated by the Roman gods, then teleported across time to fight as a soldier in every war ever fought. His "touching the earth" thing became a "ritual" to keep him sane. No, really.
David Franzoni's original script had Maximus named Narcissus, Commodus being strangled in the baths (as in RL by the real Narcissus), the fight at the Colosseum against a rhinoceros instead of tigers and Lucilla not making it to the end of the movie but being executed (as she was in reality) along with some senators inside a Sicilian Bull.