This post is directed at Wolf Kanno. It would be a bit too long to quote, you know.
I've never had isues with FF V's plot, not even with the translated SNES version (I've stayed away from Antholgy). I can agree that Exdeath's personality can be considered bland. However, I see him as an improved version of Xande. FF III and V's stories show many similarities, and their villains are no exception. You see, you are right when you say Exdeath has a backgroundstory. Just like Xande, the first FF villain ever to have a backgroundstory. However, Exdeath appeared in the game many times and not just at the end like Xande. Exdeath introduced a new villain type in FF, by re-appearing a lot in the game.
Golbez? No, he doesn't really count. Why not? Because Golbez is an improved version of Garland and Emperor. He has next to no background, but appears many times in the game. And his personality too, isn't really that much to write home about.
So Exdeath was new terrain for the creators actually. And I think that his bland personality also comes from the fact that Exdeath was never meant to live. He was a tree in which they sealed evil, and that tree later became Exdeath. His inhuman behavior (in my eyes) proves that for me.
Exdeath does quite some very evil things and not many FF villains obtain the same thing he did, like you said.
Overal FF V's story was improved over IV's in my opinion, because IV actually used the FF I and II formula and fleshed it out a bit more, while V continued on the road FF III had first walked. The road of a story with background and a villain with background. Also, I find it quite amazing how well the creators were able to mix gameplay with the story in FF V, cause with the job-system it wasn't really easy, I think, to create interesting characters. Do not take me wrong, IV's story was great too, but that was thanks to its great cast. The story itself, I found, lacked background, which I wouldn't really expect after FF III. FF V did have background (Enuo, the Void, stuff), and a lively, colorful cast. So in that way, I think V improved over IV, but I also know that nobody will agree if I say V's story > IV's story (in some ways).
And oh yeah, play FFVA, you'll never regret it.
For the rest of the villains you summed it up pretty nicely, and I didn't really mean to throw Kefka in the pile of other insane villains, I just showed the topic creator that he absolutely shouldn't complain about Kefka being insane and brainless while almost every FF villain is (except for, well, Xande, IMHO). It was weak statement against Kefka, anyway.
I'm playing FF VI Advance now, too. And Kefka indeed comes across as more evil. He comes across as a cold killer that has fun doing what he does, and I must say I enjoy it more because it is perfectly combined with his priceless lines and attitude. If it comes to pure evilness, I think Kefka wins.