In a Metal Observer review of Anata - The Conductor's Departure, the reviewer declared it "melodic, nay, harmonic metal"
This was probably due to divvying up the melody in such a way that if one guitar was not being played, it would be a boring song; with both guitars, the song becomes a beautiful harmonic melody.
Your description of two guitars playing different lines in harmony is what happens in pretty much every metal band since the NWOBHM. Since almost all metal bands use at least some guitar harmony, that reviewer is just stupid. And harmonic metal is NOT a genre.
As far as recommendations, I'm too lazy to carefully look whats been mentioned already, but here's a few:
Melodeath: Dark Tranquillity-Character and The Gallery, but everything is great
In Flames-early stuff, like Whoracle
At the Gates-Slaughter of the Soul
Hypocrisy-The Arrival
Amon Amarth-Fate of Norns (Viking lyrics, but the music is MDM)
Opeth-only sorta melodeath, but still essential. Get everything.
Into Eternity
Black: Enslaved-RUUN,Isa,orBelow the Lights for prog black, for more traditional bm, Frost
Darkthrone-Transilvanian Hunger or A Blaze in the Northern Sky
Emperor-Anthems to the Welkins at Dusk or In the Nightside Eclipse
Ulver-for bm, go for Bergtatt and Nattens Madrigal
Borknagar-Empiricism or Epic
Arcturus-Aspera Heims Sinfonia is great symphonic black, but their more famous for avantgarde black, get Diabolical Masquerade and
Sideshow Symphonies
Immortal-any
And some more bands-Bal-Sagoth, Blut Aus Nord, 1349, Summoning
Albums mentioned are sometimes personal favorites, other times widely considered essential.