It starts off with Batman lower than he's ever been before. He's hunted by the entire city. The FBI has been called in. He doesn't even have Gordon as an ally anymore (Gordon would like to be, but can't). Whoever the real Bruce Wayne is, he's getting lost inside of this monster of his, like Alfred warned him about. Batman becomes his sole state of mind. He now sees it as some sort of punishment or penance he has to pay for all the people he feels he's let down (Rachel, Harvey, his parents, etc.).
Ironically, as dire as Batman's situation has become, his FAKE Bruce Wayne persona has never been better. Business at Wayne Enterprises is booming, and they are very close to obliterating a competing corporation, which has relatively recently been taken over by Roman Sionis, the disturbed son of the founder who has essentially run his father's company into the ground in a very short amount of time. Sionis is someone who grew up in the same circles as Wayne, their parents having been "friends" (though Sionis's parents were two-faced rich folks who really only pretended to be friends with the Waynes while bad-mouthing them in private often in front of their son). I see Roman as sort of the Bizarro Wayne - how Bruce might have turned out if he didn't have great role models like his parents and Alfred. His father had kept his company afloat through lots of dirty business and ties to the criminal underworld. Well, Roman has a hard time mainting those connections, largely because these criminal figures have never had any respect for him as he's a lousy businessman. So he loses these connections, and consequently, loses his company to Bruce Wayne, who he's ALWAYS been jealous of since childhood. It's this utter failure and humiliation that makes him put on a black mask and go out and murder/torture those criminals who turned their backs on him and caused his downfall. Still uber-wealthy, he starts a gang and insists they all wear these terrifying skull masks (The False Face Society). He's got a much better knack for crime than he ever had for business, and rises to power quickly, largely through simply sadistically murdering anyone who he thinks will get in the way. Fear does the rest. He's a total sociopath. And as soon as The False Face Society is assembled, they start kidnapping, torturing, and killing Wayne Enterprises employees (even after ransoms may have been paid). But all the while, he keeps his Roman Sionis persona, a corporate failure, who's now a "retired" socialite playboy. No one in the underworld has a clue that he's this Black Mask killer. Sionis is the socialite king of Gotham's East End, and its queen would be the much more savvy, sophisticated, and charitable Selina Kyle, who is pretty much the East End's favorite resident for all of her generous contributions to the community. Little do they know that she gets her money from stealing from the many other wealthy (probably crooked) citizens of Gotham, and her alter ego is known simply as the East End Catburglar. Selina knows Sionis is a sick puppy, he's always disturbed her, and she knows his family is as crooked as they come, so she's always looking for a way to take him down.
Meanwhile, the FBI have brought in Edward Nashton to help capture Batman, and he has 100% support of the people and the police. He and his team intercept a crime scene from Gotham PD: one of Black Mask's early murders. In the interest of capturing Batman, they create a fake criminal: The Riddler. They plant fake evidence for Batman to make it look like this new criminal is responsible (the first bread crumb of their dummy trail), while Gotham PD investigates the real Black Mask case. Nashton creates fake crime scenes and uses some of Black Mask's real ones in a cat and mouse game with Batman as the Riddler. So while Gordon, Gotham PD, and Catwoman are on the Black Mask case, Batman is on the trail of this fake criminal, who they even use to communicate with Batman through the media. But Batman never completely falls into Nashton's traps (and Edward never gives away that these crime scenes are fake - Batman just thinks he's being taunted by the criminal leaving them), and Nashton becomes obsessed with outsmarting him. His methods get out of hand, and innocent people start to become collateral damage. Nashton is then taken off the case and kicked out of the Bureau. But he continues the Riddler antics, and when he's completely over the edge, he kidnaps Coleman Reese and makes it look (to the Gotham PD) like Reese is just the latest Wayne Enterprises employee to fall victim to Black Mask. Nashton remembers that Reese claimed to know who the Batman was once upon a time, and he eventually gets the truth out of Reese before killing him. Nashton plans his final showdown with Batman as some sort of media spectacle, in which he plans to reveal his true identity to the entire world, ensuring his triumph be known to the masses. He also happens to be aware of a certain killer with a MAJOR grudge against Bruce Wayne, so as an insurance policy, he leaves a little "riddle" for Black Mask that only he could understand, and a semi-alliance is formed (Black Mask & his gang will be Riddler's muscle in case things go wrong, will kill Batman after media event, or something like that).
Earlier in the story, the Black Mask killer gets on Catwoman's radar after he mercilessly kills a child (or maybe one of her hooker "friends"/informants?) in the East End who witnessed one of his murders. It becomes her side mission to find out who this killer is. In the mean time, Bruce and Selina meet the same way they did in the animated series. She buys a date with him at a charity auction, but wants nothing to do with the actual date - she just did it for charity, and she's generally disgusted by that whole social circle, so she wants nothing to do with Wayne. Bruce finds her unusual attitude refreshing, and insists that he owes her a date, so she reluctantly agrees. Sometime after that, the East End Catburglar has her first encounter with Batman, narrowly escapes, and is instantly drawn to him, and thinks he may be her soulmate. In the fray she scars his face, so when she opens the door to her date wishing it was Batman, she's ecstatic to discover (thanks to the scar) that he IS Batman. Of course, she doesn't let Bruce know any of this, but she's much more enthusiastic about dating him now, and she sees right through Bruce's fake persona and constantly calls him out on it. Everytime he tries to lie as a cover, she knows, so he's forced to be himself around her. And so begins her romance with the real Bruce Wayne. On their dates (when they're not doing thrill-seeking activities like skydiving or something), they have discussions about their outlooks/philosophies, often on the state of their city and debate about "The Batman" - Selina works to bring him out of his funk, make him feel better about what "Batman" does, convinces him that The Batman should take pride in his work and shouldn't have to answer to anyone, all without ever letting him know she knows his true identity. And while he may disagree with that general outlook, she does actually make him feel better and helps him re-think his work so far as Batman. She also fills him in on the Black Mask killer, which gives him the upper hand (of knowledge, anyway) over the Riddler in their cat & mouse game...until Riddler discovers his identity.
Throughout the entire movie, Selina is planning her biggest score yet: Roman Sionis's estate, the most secure building in Gotham. She decides that Batman's big media circus with the Riddler is the perfect time to make her move, so she does, since she's completely confident that Bruce can handle the Riddler. Yet while she's in there, she discovers evidence that he is Black Mask, along the message (or something) from the Riddler, and she realizes just how much danger Bruce is in. She leaves her score behind to help him. In the final confrontation (where perhaps Black Mask or Riddler has kidnapped Lucius Fox to draw Batman out), Catwoman saves Batman and kills Black Mask (her 1st and only kill), Batman neutralizes (don't really care how) Edward Nashton, who's now pretty much decided he actually WAS The Riddler, and Batman "catches" Catwoman and unmasks her. He's shocked and hurt to discover it's Selina, who pleads with him to let her go, arguing that if she goes to jail and her reputation is destroyed, her charities will crumble. He insists that she pay for her crimes anyway, and that if she had truly loved him, she would understand that. He leaves her chained or handcuffed to something for the police, but he subtley leaves her an escape. And surprisingly...she doesn't take it. The movie ends with Selina facing her worst fear - a cage - for Bruce, and Bruce takes the reigns on all of her charities, causing the media to be all abuzz over this new direction - "Bruce Wayne: Philanthropist?" The citizens of Gotham call for the return of the batsignal (during this media circus, the whole truth came out about the villains), the FBI falls back due to an internal affairs investigation over the whole Edward Nashton ordeal and all the innocents that died because of them.
The theme is redemption: Batman is redeemed in the eyes of Gotham's citizens, Gotham's citizens are redeemed in the eyes of the audience (since they were essentially "villains" throughout most of the story), and Selina is redeemed in the eyes of Bruce. She's restored his faith in humanity and given him a new outlook on WHY he does what he does: He's not Batman because he's paying a pennance anymore, and he's not Batman because he has to be; he's Batman because he WANTS to be. And this is the arrival of that "Dawn" Harvey Dent spoke of in TDK. For once, everyone in Gotham, including Bruce Wayne, has hope and contentment with their situation.
Sorry if this is all a bit jumbled, but it all kinda came to me at once after I read that great Riddler concept, so kudos to whoever came up with that. And yeah, I'm totally fuzzy on the details of how it would all play out. But cheers to anyone who actually managed to read all that. I probably would've given up somewhere around the middle.