My first thought was Gul Dukat: the perfect recurring Star Trek villain. Villainous, he's always a threat when you see him (even when he's being peaceful, there is always a threatening undercurrent), he does have a complex background and motivation, but it never really takes away from him being a nemesis, and he's always around to make trouble when inconvenient for the heroes.
The Vorta and Jem'Hadar were great. The Jem'Hadar were the best grunts, and the Vorta were wonderfully slimy and devious commanders. The Dominion was even better than the Borg as Trek villains, as the Dominion was dangerous, but they were enough like us we could relate to them a little better, and although they were stronger than the Federation, they were not so impossibly powerful that victory seems implausible. As Vigilance said, in many ways they were the Anti-Federation.
The Maquis were good as an occasional antagonist. Showing that the Federation isn't perfect, and that humans really do make mistakes. A conflict where both sides see themselves as the good guys, and a chance to take a close look at what the Federation is really about.
Section 31 is a good antagonis for much the same reason. In a dangerous galaxy filled with other super-secret spy agencies like the Obsidian Order and the Tal Shiar, with threats to the very existence of the human race on the scale of the Dominion and the Borg, it was somehow reassuring to know that the Federation had it's own "dirty tricks" arm, but also that menace from within, as the Federation has to look after its own