I think Paladin taking from Conj is important but it does not need to be the cure spell, the cure spell can be something paladins take when soloing and that is ok, I think what is more important is that there is enough variety for the paladin among other skills from Conj and MRD.
Leave Paladin with Con.
Give Paladin back the BIG HEAL(save your azz) with longer cool down. It's a trait of Paladins.
I like the idea posted about adding mind or another mod on pal weapons to help mod the heals. Really like this idea!!
Another option is to open so that jobs can use more cross classes skills. Just don't let them fully use skills till the other class(s) leveled above set level. Same level as current job, or even 50. Spent the time leveling a class show commitment.