A mage would be an interesting main hero, and a rather nice change, perhaps.

Pirate or viking sounds good. Especially viking

Perhaps even an archer main character, but I guess archers and mages aren't really seen as "heroes" in comparison to knights and thieves.