They are immune to the spell
I will begin with the statement that all spell descriptions are rules, the text is not merely flavor text. In fact, the spellcasting rules refer to everything in the spell's description as the effect of the spell (emphasis mine):
Each spell description begins with a block of information, including the spell's name, level, school of magic, casting time, range, components, and duration. The rest of a spell entry describes the spell's effect.
The description for harm, as noted in the question, begins:
You unleash a virulent disease on a creature that you can see within range.
The effect of this spell is to unleash a disease upon the target. Both the damage and the reduced hit point maximum are the result of this virulent disease. If the target of harm is immune to all disease, via the paladin's Divine Health class feature or any other means, they would be immune to any effects of the disease. In this case that would confer immunity to both the damage caused by the disease as well as the lasting effect.
Therefore, it follows that disease immunity gives full immunity from the harm spell and any other spell that specifically causes its effect through disease.
This ruling is also supported (in an unofficial capacity) by a tweet from lead rules designer Jeremy Crawford:
Immunity to disease makes you immune to the harm spell.
