If a dash of sci-fi mixed with fantasy doesn't bother the OP, then I recommend Edgar Rice Burrough's "Barsoom" novels (aka the John Carter of Mars books). Mostly swordplay, between men and against the occasional beast.
Burroughs' stories are quite intriguing, and although the series is following one central character, occasionally a book will revolve around another entirely separate hero/heroine.
If you like strong codes of honor and righteous protagonists, start with "A Princess of Mars", and take it from there.
