Well ... keep in mind that I haven't seen Sword of the Stranger - but I'm going to assume it involves a lot of violence, and possibly ... sword-fighting?
Okay ... no idea what you've seen so far - but going along those lines, I'd say Rurouni Kenshin, Seirei no Moribito and Blade of the Immortal. Maybe Samurai 7 - but I found Samurai 7 pretty slow going at some points.
If you don't mind moving away from the swordy stuff ... and looking for some comedy as well, you can possibly give Ranma 1/2 a try (Sou1Co11ector, this one for you as well) - it's pretty old, but there's a lot of ridiculous fighting and it's pretty damn funny. Staying with the funny fighting stuff - History's Strongest Disciple Kenichi is also worth watching.
Sou1 - Ranma & Kenichi for you as well

Sumomomo Momomo also has some fighting in it, but it's basically a harem anime - also has some ecchi elements. You can also look out for Sekirei, and Sekirei ~Pure Engagement~ if you need some ecchi - try and track down the uncensored versions though. To LoveRu is also harem/ecchi type - animation and character design very awesome, with good comedy moments.
Some others you can take a look at (if you haven't seen them yet):
Mai HiME and Mai Otome - Sci-fi/Fantasy/Action
Kaze no Stigma - main chicky reminds me of Chidori in FMP - supernatural/action
Ikkitousen - Action - plenty of ecchi
Shakugan no Shana - action/supernatural + a bit of moe.
I'm a little out of touch with the latest releases (Just finished Highschool of the Dead the other day), so I can't help you much there