2. "The Siege of AR-558". Unlike some posters above, I don't see the need to avoid the Dominion War entirely, as long as you aren't getting too deep into the weeds of the plot. "The Siege of AR-558" is easy to understand and doesn't really "give away" much that would "ruin" the series for anyone. I think also that at least episode on this DVD with some phasers and explosions is a good thing. (It probably also wouldn't hurt that this is the DS9 episode closest in tone to 21st Century sci-fi like The Dark Knight and nuBSG.)
You make a good point... Can we really have a DS9 'best of' without the war in it? It is, after all, one of its distinguishing characteristics. "The Siege of AR-558" is the most suitable for an introductory disc out of the Dominion war arc, but I couldn't remember if it spoils much or not... I will rely on your opinion that it doesn't.
So - my revised list - taking into account the versatility, which characters feature heavily in it, whether it is a good introduction to characters/plots etc.:
(man, I am thinking too much about this

You think that someone is reading this and taking suggestions from us?

)
"Duet" - first of all, it is so great would just be wrong not to put it; and it is standalone, while it also gives a good introduction to Bajor/Cardassia/occupation
"The Visitor" - accessible emotional SF story, standalone, also introduces the Ben/Jake father/son relationship which is a big part of the show
"The Siege of AR-551" - the most accessible episode from the Dominion war, and one of the best, doesn't require too much knowledge about the context of the war; and you have to have an episode with a bit more action
"Trials and Tribble-ations" - best comedy episode, very accessible, and works particularly well for non-Niner Trek fans and people familiar with TOS and its characters; also has the advantage that it introduces a bunch of characters well - Dax, Bashir, O'Brien and even Worf are at their comedic best, Odo and Sisko are also heavily featured. This way you have most of the show's main characters introduced quite well, since "Duet" is a great Kira episode, "The Visitor" is Jake-centric, and "The Siege" has some great Quark moments (and Nog and Sisko, of course).
Let's say there was a follow-up disc for DS9, "The Best of DS9 II":
"Necessary Evil" - an awesome noirish Occupation episode; also gives a good introduction to Odo, Kira, Quark and Dukat
"The Wire" - an interesting episode that keeps you guessing, and an excellent introduction to Garak, but still keeps him mysterious enough
"Nor the Battle to the Strong" - because it is great, more or less standalone, it doesn't spoil much, and it is is focused on a war - even if it is not *the* war
"The House of Quark" - one of the best comedy episodes, best Quark episode, a good Klingon episode as well; the only thing that would be "wrong" about it is that it would give the first time viewers the idea that all Ferengi or Klingon episodes are that good... but that's good, because it might make new fans more willing to tolerate the Ferengis early on
(alternative: "Little Green Men", another funny Ferengi episode)
Great episodes that I would not put on the Best of disc:
"The Maquis" - two-parter, would take up too much space on the disc
"Second Skin" - wouldn't have the same emotional resonance without knowing the characters and the context already
"In the Pale Moonlight" - same thing as "Second Skin", plus it would spoil too many things
Anything else related to the Dominion, the Maquis, Section 31, Bashir being genetically engineered, etc. - anything that has too many spoilers, and needs context
"Far Beyond the Stars" - doesn't give an idea what the show is about, and loses some of the fun when you don't know the actors/their usual characters already