I quite enjoyed Arkham Asylum's story. The concept of it was simple enough. Joker takes over Arkham to make Titan monsters, but it kept revealing little twists and turns along the way like Gordon getting kidnapped, Dr. Young being revealed as a lackey who was draining Bane's blood for the Titan, the Amadeus Arkham stuff, Joker injecting Ivy with the Titan etc. There was some semblance of a story there. It had a good flow. Apart from Bane all the characterizations were great. Joker, Harley, Scarecrow, Ivy....they were all great.
In Arkham City, there is no proper story. It's basically just chase the cure with a little sub plot about protocol 10 thrown in at the end. Which is a shame, but the amazing gameplay makes up for it. There is also more 'off' characterizations in AC like Strange, Two Face, and Bane again. Joker, Penguin, and Mr. Freeze are the best written characters in the game.
I would love if Origins got a great story to match the gameplay.