I'm not that much into lore, but I gather that Malakims are supposed to be the religious guys.
What about giving them the ability to build all religious heroes regardless of their religion.
They will be able to build any religious hero in their cities with the according religion, if they have the necessary techs.
If this is too strong or too easy for them, limit the ability to holy cities from different religions, so that you virtually have to found other, additional religions in order to build the according heroes.
Some techs and thus heroes would be locked anyway (hidden paths, arete) unless they change religion to research those.
It would be fun to collect religious heroes, but you had to put a lot of effort into it regarding research and possible switching of religions.
What about giving them the ability to build all religious heroes regardless of their religion.
They will be able to build any religious hero in their cities with the according religion, if they have the necessary techs.
If this is too strong or too easy for them, limit the ability to holy cities from different religions, so that you virtually have to found other, additional religions in order to build the according heroes.
Some techs and thus heroes would be locked anyway (hidden paths, arete) unless they change religion to research those.
It would be fun to collect religious heroes, but you had to put a lot of effort into it regarding research and possible switching of religions.