I'd probably listen to them in chronological order. 'The Age of Cataclysm' first, then 'A Coming Storm', then 'Of Shadows...and the Dark Things You Fear'. There's not really much between them overall, but each one has quite a different overall feel to it, despite the fact that they have a very definite style, and quite a narrow lyrical focus (Apocalypse, Medieval Satanism, Death, Mechanised Warfare and combinations thereof). I do enjoy a good bit of the old melodic BM myself, but no-one on quite the same level as these guys. The strange thing about them is that they sound somewhat generic, but not really like anyone else: they have a dash of old-school MDM to them, and an almost impeccable restraint as far as the use of keyboards go (overuse of keyboards and Dani Filth vocals are the two things that most often sink Melodic BM bands). They're also pretty admirable for having a female member and not making her sing.
Actually, speaking of overuse of keyboards and Dani Filth vocals, have you ever heard Illnath?
Illnath - Cast Into Fields of Evil Pleasure
The best description of these guys was provided by a friend of mine "Hey, it's kind of like Cradle of Filth, but it's more guitar driven and doesn't suck balls"