This i can wrap up in a simple nine words... Hard Boiled Wonderland And The End Of The World!!! Definitely recommend it, the authur Murakami is expected to win the nobell prize any year now. Well besides that rant, time to get down to buisness.
Story: Ill try not to refference Murakami's work that this story is bassed off to much and stick to Haibane Renmei on it's own. Haibane Renmei has a theme rather then a story, a vision of heaven with it's own uniqueness and unpredictableness. The main charecter is named Kana who is wiped of her previouse existence from her past life. The enviornment in the story is a metropolis (plot hole free!) were life moves on untill the day of flight were an angel may make there exodus from the so called heaven.
Animation/ Sound: Early noughties anime has always been my personal favourite era in the short history of Japanese animation so I can safely give it the ok. The animation/music and general theme work together in great harmony as if they were ment to be merged together. The music was so well written that it allows me to pay attention to Ko Otani its conductor.
Charecters: I would say that the charecters are two dementional and well... animated. But to be honest, they need to be as false as possible. If the anime gave them more personality then the entire anime's equilibrium would be spoiled. So its safe to put the charecters in a critic way in the grey. The main charecters are angels after all so theres no need for putting there ego into the picture "book refference" (sry!).
Overall: What can I say.... "everything is perfect, perfect comes from perfect, take perfect from perfect and the remainder is perfect" Just relax, turn your bran on or off and enjoy :)