Definitely Sarevok. Both Irenicus and Melissan are too cheesy for my tastes.
Sarevok has also the most detailed character and agenda out of the three, and both of these are executed in a more subtle manner than Irenicus` or Melissan`s. We only get to see bits and pieces of information about what Sarevok is trying to accomplish and at the beginning, we do not even know who he is, we only see the results and consequences of his actions throughout the Sword Coast, and this alone already makes him a more interesting antagonist than the other two. The way his plans are being revealed only bit by bit and then eventually foiled by the player character creates a focused and coherent plot while also providing a driving force for the player and the enjoyment of uncovering a mysterious conspiracy behind the unusal events.
This is only a matter of personal preference, but Sarevok`s story is also a bit more "low-key fantasy" and not as melodramatic as the story of Irenicus, which is also one of the reasons why I like him best. He is a very charismatic and criminal mastermind who also happens to be one of the stronger children of the Lord of Murder and does not hesitate in trying to take up his heritage. However, if the player lets him join the party in ToB, he can also discover a more bitter and down-to-earth side of the character.
Irenicus had a few good lines, but that`s all that he had going for him, and between his hubris and Sarevok`s, the latter`s one has more depth to it.
As for Melissan, well...it was quite obvious from the first time she opened her mouth that she would be the final villain. She was simply an uninteresting and sort of an uninspired character.
Combat-wise, Melissan is without doubt the most difficult. I'm struggling with that right now for the first time, and it's doing my head in. Sarevok was tough too, not least due to his friends. Irenicus, however... I didn't expect the fight right where it happened, so we started it totally unprepared and unbuffed. Still we kicked his ass without deaths.
Melissan > Sarevok > Irenicus.
As a villain, I agree with all of the above by szablev. The way the game lays out Sarevok is much more pleasing and interesting than in BG2. At first we don't know anything, and then we slowly put the pieces together and then fight him. It's also not really a "Save the world" scenario, which I enjoyed as it breaks with the norm.
Irenicus may be more fleshed out in terms of his motivations, but there is something that's hard to put your finger on that doesn't sit quite right with him. A failed love story makes him want to become a god? Errr. It gives him a more human "face" to be sure, and I actually felt sorry for him, but I thought Sarevok worked better as a villain - not least because of how the game doesn't start off with "SAREVOK is the BIG BAD VILLAIN" from the first second.
Melissan is ridiculously hard to beat, but as a villain there really isn't much to her. It was pretty obvious from the time we met her she was going to be YET another person who would soon backstab us (seriously, how many such NPCs are there in the games? 900?). We do get a little backstory, and that was nice, but there is too little too late to either identify with her or start to detest her.
Sarevok > Irenicus > Melissan