The Four Horsemen of Apocalypse is an idea astoundingly elegant for its simplicity: if you're going to have a villain named Apocalypse, giving him a group of henchmen and naming them after the biblical four horsemen is a no-brainer, and it's a concept that has survived right alongside Apocalypse as a character for several decades now (barring that brief period of time in which Apocalypse traded in horsemen for the Image-riffic Dark Riders/Riders of the Storm).
Though they weren't around for the first appearance of Apocalypse (as the character was a last minute swap for the Owl as the mysterious leader of the Brotherhood of Evil Mutants wannabes, the Alliance of Evil), his next appearance immediately set about rectifying that, as he popped up in a handful of issues, gathering an assortment of mutants. That group (minus Death) was unveiled shortly before "Fall of the Mutants", and since that storyline, while their membership (and in some cases, the designation of who is which Horseman) has changed, it's not often that Apocalypse doesn't show up without some combination of Horsemen at his beck and call. Here then are some of the more notable arrangements.
Abraham Kieros (War), Autumn Rolfson (Famine) the Morlock Plague (Pestilence), Angel (Death).
Apocalypse's first batch of Horsemen are a mix of new and existing characters, and aside from being the first, they remain a memorable group simply because their gathering was depicted in detail through early issues of X-Factor, as Apocalypse gathered his followers and transformed them, one-by-one, culminating in the reveal of the thought-dead founding member of the X-Men Angel as Death. With their unified gold masks and montrous-looking mechanical horses, it's tough to beat this original grouping.
They also briefly popped up again in "The X-Cutioner's Song" (albeit without Pestilence, who died during "Fall of the Mutants"), with Caliban (who left X-Factor to join Apocalypse in that story) taking over for Angel as Death, but the group is dispatched relatively early in the story, and only Caliban returns after that as a Horseman in future stories.
(This is also the iteration of the Horsemen that appeared in the X-Men animated series in the 90s).
Best of the Bunch: The reborn Angel is clearly the standout of this assortment, but I've always had a soft spot for Pestilence, the other existing character transformed into a Horseman.
Age of Apocalypse
Holocaust, Abyss, Mikhail Rasputin, Mr. Sinister
A testament to Apocalypse's impact on the X-books, 1995 saw a massive franchise-wide event built around the idea of time travel creating an entirely new world in which the villain reigned supreme, complete with all the X-titles being formally cancelled and relaunched as new books set in the dystopic new world. With his control over the United States nearly total, Apocalypse's horsemen serve more as regional governors than henchmen, eschewing the biblical classifications for the most part, With Mikhail barely appearing and Sinister working behind the scenes to overthrow Apocalypse (through the creation of Cable-surrogate Nate Grey), Holocaust and Abyss are the two Horsemen who get spotlighted the most as out-and-out villains arrayed against the heroes.
Best of the Bunch: The AoA Mr. Sinister isn't terribly different from the regular version, and Mikhail barely appears in the event. Of the remaining two, it's Holocaust who leaves the most lasting impression, just on the strength of his design and his sheer devotion to Apocalypse's creed.
Deathbird (War), Caliban (Pestilence), Ahab (Famine), Wolverine (Death)
A group composed entirely of existing characters serving (or made to serve) Apocalypse (complete with Caliban as the first Horseman to trade one classification for another), this group operated during "The Twelve" storyline, a massively-disappointing attempt to payoff a plot thread lingering since its introduction in X-Factor #14. It's also the story which, while teasing the death of Wolverine, also saw the character reclaim his adamantium skeleton (after one notable previous false-start) as part of Apocalypse's efforts to transform him into Death.
Best of the Bunch: Wolverine being brainwashed into serving as Death and getting back his metal skeleton makes him the most notable of this bunch, but the character design is pretty awful. Give the nod to Caliban then, for snatching a second Horseman position (though full disclosure, I hold this story - and this batch of Horsemen - in low regard, just for the way it promised to resolve a loooong simmering plotline, then did so in a manner that completely ignored most of what had been teased about the plot previously).
Blood of Apocalypse
Gazer (War), Sunfire (Famine), Polaris (Pestilence), Gambit (Death)
Peter Milligan's run on X-Men isn't terribly well-regarded, but it's not entirely his fault. At the time, he was coming off an acclaimed run of his own (on X-Force/X-Statix) that likely raised expectations too high, and was taking over the book in the wake of first Grant Morrison's much loved retooling of the series as New X-Men, then Chuck Austen's flailing attempts to pick up the pieces left by Morrison and craft them into a workable serialized storytelling engine again, and finally, the ramifications of House of M/M-Day (which found the vast majority of mutants rendered powerless by Scarlet Witch). Milligan just never clicked on the book, having seemingly run out of things to say about the characters, leaving his stories somewhere between atonal and weird. Perhaps as something of a Hail Mary, his final big storyline involved the return of Apocalypse with a plot to kill off 90% of humanity (echoing the recent decimation of mutantkind), and a new group of Horsemen, once again culled entirely from existing characters (though in the case of Gazer, just barely).
And that's partially why this group never quite worked - one mind-altered X-Man-turned-Horseman is fine; three just seems like too many (especially when all of them are going to ultimately rebel against Apocalypse by story's end). This story also saw Polaris, one of the increasingly-few notable characters to lose her powers as a result of M-Day, regain her abilities, and also featured the debut of a new power for Gambit: the ability to generate and disperse poison gas, making this the start of Deadly Fart Gambit, the less said of the better.
(Interestingly enough, this story also stands, to date, as the final appearance of Apocalypse in the present day, in his traditional form).
Best of the Bunch: Gazer, I guess, just for being plucked out of obscurity for the role and not getting stuck with the power of farts in the process.
The Final Horsemen
Decimus Furius (War), Jeb Lee (Famine), Ichisumi (Pestilence), Sanjar Javeed (Death)
Introduced in the pages of the relaunched spinoff title Uncanny X-Force, the so-called Final Horsemen were gathered when a cult of Apocalypse worshipers managed to revive their leader, albeit in the form of a child. It was then revealed that Apocalypse had selected these four individuals from across various eras of time to serve as his final Horsemen should all else fail. Comprised entirely of new characters, the idea of Horsemen culled from different eras is interesting, but the group as a whole suffers from having some vague-yet-oddly-specific Morrisonian powers (like "the ability to generate a living sound cancer via percussion") and also having to compete with each other for page space in order to receive any characterization. As a result, they don't really standout from one another beyond their individual gimmicks (War is a Minotaur, Famine an American Civil War Era-spy, etc.) and their (admittedly strong, thanks to the work of Jerome Opena) individual designs.
After Archangel became possessed by a remnant of Apocalypse left in his psyche (or something like that), and Sanjar Javeed was killed, he brainwashed Psylocke into briefly serving as the Horseman of Death in Javeed's place.
Best of the Bunch: Again, I can't really tell you too much about each of these characters as individuals, but the eerily-quiet and haunted Jeb Lee is the one of the bunch that I remember the most vividly.
Archangel, Storm, Psylocke, Magneto
To it's credit, the upcoming film, which features Apocalypse as its main villain, maintains the idea of Apocalypse being served by four horsemen, and fills those roles with three new characters (to this iteration of the film series, at least) and one existing character (Magneto). I haven't seen it yet, so I don't know if each character is assigned a specific Horseman designation, but just seeing that the idea is being applied to the film is appreciated. Given that Storm is destined to join the X-Men, Magneto rarely marches to the beat of anyone's drum but his own, and the other two Horsemen are, outside the film, longstanding X-Men in their own rights, I expect there will be a fair number of Horsemen rebelling against Apocalypse beyond the usual "the one he brainwashed the most breaks free" routine.
Best of the Bunch: Hard to say without having seen the film, but the idea of Magneto as a Horseman of Apocalypse is the most intriguing on the surface.