I went through and built up a build for you, trying to follow what you said in the thread. It goes through level 69.
Skyrim Perk Calculator - Plan the perks for your Skyrim character before spending them!
I kept what you said about smithing. Block, I would take everything, as a 1h pally relies heavily on it, and the perks are great on both sides. As said above, the heavy armor can be trimmed down some on the first perk, as you will not need all 5 points, i usually put in 3 though, to help out early - mid in the leveling process. As wanting to RP, pallys are generally blunt, so i put perks in for maces. I am not sure about any bugs with the system, but the stun at the top seemed a good fit too.
On speech, I found it fairly useless to go past investor, as after that point with speech, you will have more money than you need, especially as a paladin, so you save some points there.
In magic, I stuck with the resto and alteration schools. In resto, you don't really need 2 points in recovery, as with the cheaper spells, and 1 enchant, you will never run out of mana healing yourself when needed. The necromage perk would be a good pally fit though. Alteration, you could go up to master, but by about the time you can get all the magic resist perks in the game, your armor will be maxed, and you will not need the flesh spells to supplement armor.
You mentioned wanting to stick to destruction for a "holy fire" concept. I had toyed with this idea myself, and decided against it, as I didn't think it really fit with the casting animations. If it was a fire strike from the heavens, I would have gone that way. The more logical issue with it is that you might not use it much. You will just be switching your mace/weapon for another weapon really. As suggested, if you do, might want to only do it on undead. I found the switching to be more of a pain than anything in the middle of combat with other characters, and only switched when I needed to for resto on my pally, and used more humble means to defeat my enemies.
I liked what was said above about using illusion. The calm spell is definitely pally, especially against humans sentient races. Good luck with the play through, hope I helped a little.