Naga is in a bad spot. It's inferior to a genie in pretty much every way. 

Even against magic immune enemies genies can just summon creatures to take hits, whereas you need to spend mana on nagas to get them into a fight and then you have a decent damage dealer.

That doesn't even account for strategies, where you split your genies into several stacks, using single genies to song of peace an opponent for several turns, while other creatures pick them off.

Nagas get the upper hand, once Genies run out of mana, but usually battles do not last long enough for that to make a difference. I always pick Genies over Naga 100% of the time.

But HoMM 4 is full of decisions like this. Cyclops vs ogre mage is another, where the ogre is so much weaker than the other choice, that you should never consider it. Griffin/Unicorn, Angel/Champion, Vampire/Venom spawn, Medusa/Minotaur, Gold Golem/Mage are other very lopsided matchups in favor of the first creature.