Babylon 5 was also excellent, especially if you just don't watch the fifth and final season.

DS9 is about to come out on DVD, at least in the states. Maybe your local video rental store will carry it. The first season is not particularly good (it's not bad), but force your way through it. There's a lot of setup in there for later seasons. Actually, the same could be said for Babylon 5, too.