I nominate Oath of Swords
by David Weber, Book One of his War God / Bahzell series.
Available in the Baen Free Library...
Our Hero: The unlikely Paladin, Bahzell Bahnakson of the Horse Stealer Hradani. He's no knight in shining armor. He's a hradani, a race known for their uncontrollable rages, bloodthirsty tendencies, and inability to maintain civilized conduct. None of the other Five Races of man like the hradani. Besides his ethnic burden, Bahzell has problems of his own to deal with: a violated hostage bond, a vengeful prince, a price on his head. He doesn't want to mess with anybody else's problems, let alone a god's. Let alone the War God's! So how does he end up a thousand leagues from home, neck-deep in political intrigue, assassins, demons, psionicists, evil sorcery, white sorcery, dark gods, good gods, bad poets, greedy landlords, and most of Bortalik Bay Well, it's all the War God's fault. . . .