He should probably start out w/ a respectable amount of experience so that he isn't promoting every time he wins a battle, but really the part about him that is too easy is the AI. He should be leading an army or at the very least a band of marauders, not wandering aimlessly about the country side. He shouldn't be a super difficult unit to kill by himself, but he shouldn't BE by himself. Perhaps the AI in BtS will improve this, or can be improved to affect this.
I agree. In my first .23c game, I was really getting pounded by the raging barbs. I counted 40+ in the boundaries of my two cities. Orthus spawns late, but somewhere else. With all the barbs in my territory, he was an easy kill for an AI civ. In a few turns I noted that Orthus' Axe had changed hands.
Another thing that would improve him is letting him heal (as Gabriel mentioned) and lose interest in pillaging. I have found it very easy to kill him when he is pillaging a farm, for example.