A campanha vai começar no 1º nível? Não sei se ainda vale, faz tempo que não jogo 3.5, mas qualquer coisa que faça você poder ser um hospitalario (classe de prestigio) o mais rápido possível. Alguns niveis de clérigo também ajudariam, caso você não se importe de não ser um paladino puro.

Uhm, eu trocaria INT e DEX para poder aproveitar o bônus de +1 máximo de DEX na CA da Full Plate.

Cara, Paladino não é uma classe forte, nem de longe. Ela é especialista em combate montado, que ninguém nunca usa.

Uma alternativa é usar uma classe de prestígio do Book of Exalted Deeds que dá muita porrada.

Outra é fazer multiclasse com Sorcerer, focar em Carisma, um talento Divino que dá CAR em CA, e ser um gish com ótimas defesas.

Outras alternativas são usar o Crusader do Tome of Battle, ou fazer um Cleric com domínio da Guerra e dizer que tu é um paladino.

Estou pensando em trocar a Constituição pelo Carisma, ficando com Carisma 16 (devido ao -2 do meio-orc) e Constituição 17 (retirado os -2 e ficando o valor original). Daí, comprar os talentos Expulsão Adicional e Força Divina. Este último me permite converter expulsões em um dano adicional igual ao meu modificador de Carisma, durante um número de rodadas igual meu modificador de Carisma.
Isso significa que darei +3 de dano durante 3 rodadas, podendo usar isso 8x ao dia, o que significam 24 rodadas com +3 de dano (ou seja, quase o tempo todo).

É a melhor opção que achei. O que acham?

Nao sei se vale pra vc, mas eu fiz um paladino badass na última campanha com o livro dos seres demoníacos lá (fiend codex II ou coisa do gênero).

A raça é irada por si só, mas a prestige que eu peguei (hell reaver se não me engano) é muito irada.

Se quiser fazer paladinos não ortodoxos, dá uma olhada lá.

Outra coisa que vc pode fazer também é usar escudos como o capitao américa. É batido pra 3.x mas deve funcionar.

O Ordained Champion também é uma classe de prestígio muito boa (ganha talento, magias, bônus no ataque e dano...) e não vai te fazer mal uns níveis de clérigo da guerra.

No momento eu tenho 2 personagens:

Dyuss - Hellbreed paladino 3 (vai virar grayguard e hellreaver)

Dante - humano clérigo 2 / guerreiro 2 / Ordained Champion 3 (se não me engano) Tripper mó-da-fo-ca cheio de magia de auxílio. Campanha de Kalamar, clérigo do Old Man, ainda trocando expulsão por Call to Arms 

Sobre a raça e atributos

Sugiro utilizar o Desert Half-Orc do Uneerthed Arcana. Ele dá +2 de Con e -2 de Int. Como Paladino, melhor perder Int do que Cha. Ele perde Darkvision porém. Além disso, o Half-Orc tem um bom substitution level no Races of Destiny, no qual vc ganha d12 de HD e Intimidar no lugar de Diplomacia.

Assim, os Atributos seriam STR 16, DEX 10, CON 18, INT 12, WIS 15, CHA 17. Foque-se somente em STR e CHA, pois você já tem WIS suficiente para lançar todos os níveis de magias de Paladino (a menos que tenha intenção de ser fullcaster).

Sobre a progressão em si

Feats. Considere Divine Might, Divine Shield, Power Attack, Leadership, Awesome Smite e Battle Blessing , Holy Warrior. Isso se vc não quiser enveredar pelas manobras do Book of Nine Swords e pegar Martial Study/Stance - imho, vale à pena: existem muitas manobras boas por lá.

No nível 5, troque sua Special Mount pela alternative class feature Charging Smite.

De PrC, considere Knight of the Chalice, Pious Templar, Gray Guard e/ou alguma outra que avance seu nível de conjurador. E, ah, Ordained Champion não é uma boa para você.

De resto, sword'n'board e Full Plate. 

Valeu pelas sugestões, dmandrak, mas elas realmente são... pouco ortodoxas. O mestre é um adepto de forgottem realms e bem old school, já jogando há 20 anos e gostando de se limitar ao mais básico possível.
Ele permitiu coisas presentes nos livros básicos, de classe (Complete Divine, etc.) e nos suplementos de Forgottem Realms. Mas nada esdrúxulo demais - ainda mais porque o personagem tem de ser um cosmopolita de Cormyr (onde a campanha vai se passar).


Bispo: suas sugestões são muito boas, mas d&d não é meu idioma nativo no RPG, então deixa eu tirar umas dúvidas:

Feats. Considere Divine Might, Divine Shield, Power Attack, Leadership, Awesome Smite e Battle Blessing , Holy Warrior.

Onde acho esses três últimos talentos?

No nível 5, troque sua Special Mount pela alternative class feature Charging Smite.

Onde acho essa opção?

De resto, sword'n'board e Full Plate.

Suponho que sword'n board seja "espada e escudo", né?
Sendo assim, fica também esta dúvida: não é melhor uma espada larga ou coisa assim? Com uma Armadura Completa +1 já vou ter 19 de CA, com um amuleto de armadura natural +1, 20 de AC. Posso trocar o amuleto por um escudo grande +1 (não tenho dinheiro pra ambos) e vai dar +4 de AC, ficando com 23.

Mas aí eu não posso bater com a espada usando as duas mãos (bônus de FOR x1.5, indo pra +6) e dou apenas um 1d8 de dano ao invés de 2d6.
Vejamos:

Com o escudo grande+1 terei:
CA: 23
Dano: 1d8 + 1d6 (flamejante) +4 (bônus de FORÇA) + 3 (Divine Might)

Com espada de duas mãos e sem escudo, terei:
CA: 20
Dano: 2d6 + 1d6 (flamejante) + 6 (bônus de FOR x1.5) + 3 (Divine Might).

Não é melhor espada de duas mãos?

Bem legal a história que postou aí, cara. Lembra umas situações de jogo pelas quais já passei e uns novatos surpreendentes no roleplay.