Plus, if you pick a Paladin, you can also skip taking a Cleric with you, because the Paladin can do everything you will ever use a Cleric for: casting Bless.

Double optimization!