I'll echo that DS9 (like every Trek show) starts slowly (and weakly). There are several good early episodes, but they are few and far between. If you start with the season finale of Season 2, which introduces the Dominion with the Jemhedar and Vorta, you'll do pretty good from there forward. Myself, I think the best place to start is at least with ep 23 of season 2, The Wire, which is a tour de force for the former Scorpio killer, Andrew J Robinson. That way you'll also see the reintroduction of the Mirror Universe (which will appear a few more times later in the series) and you'll also catch one of the early "let's torture O'Brien" episodes, which are generally very good.
The war arcs don't really start until Season 4 with the reintroduction of Worf from the TNG. Season 3, with a few exceptions (Meridian, ugh; Fascination, double ugh), is still very good though.
If you want to watch any episodes in Season 1 or 2, the ones to see are:
Season 1
11: The Nagus (though not as much if you don't like the Ferengi)
19: Duet: Very well acted.
20: In The Hands of the Prophets: For the introduction of Vedek/Kai Winn.
Season 2
1 2 and 3: the opening 3 part-er about the Circle is quite good with a great performance from an uncredited Frank Langella
7: Rules of Acquisition: This plot point will be referenced in the future. Not the greatest episode though. Again, if you hate the Ferengi, skip it.
8: Necessary Evil: DS9 does a murder mystery. Okay, but not great.
13: Armageddon Game: The beginning of the O'Brien/Bashir friendship
14: Whispers: More, torture O'Brien. Nice episode that has you guessing throughout.
20-21: The Marquis: Not a great episode, but introduced the idea of a plot point that would reappear multiple times and even be the basis of the next Trek series, Voyager.
Oh, and something that will *really* enhance your enjoyment of Deep Space Nine, would be getting a hold of one of the best Companion books in the history of the genre,
Deep Space Nine Companion.