Hey there JayB. I don't know how much help this will be to you but it's important not to consider music theory as rules. Music theory is merely a list of the conventions that have developed in western music over the last 1-2000 years. At most you might consider them as guidelines but the best advice I can think of is simply to use your ears and play whatever you think sounds right. The same applies with harmonising - there are conventions, yes, but there are no right or wrong ways of doing things. Just allow your mind's ear to work its magic.
For your interest -
Nice!... This sequence is quite open to interpretation but I'd be inclined to suggest trying C_Dorian mode (scale) here. You'll get the C_Minor aspect from it, but the scale also includes a major 6th (A) which will meet your DAD chord, fifth along in the sequence. The Dorian mode isn't particularly metal to my mind - it has a laid back minor feel to it and was embraced extensively, and then perverted, by Bebop Jazz back in the day - but such things are subjective and how good a musical scale sounds probably depends on what a person does with it, musical context etc.
Failing that you could try regular C_Minor, C_Phrygian, C_Minor_Harmonic, even C_Blues, or any combinations thereof, depending on how far you wish to stray from strict harmonic convention.
Harmonising is harder to explain. A good starting point might be to do what others have suggested here and try moving your melodies up (or down) 3rds, 4ths, 5ths (within the scale you're working in!), but I think with time it will become clear that there are different styles of harmony and that certain kinds of melodies will lend themselves more favourably to certain harmony styles over others.
Yes indeed, I believe the main body of that guitar part was in an unidentified species of E_Minor, though the occasional A Major chord that comes in hints at a Dorian mode, so yeh man - would definitely recommend the C_Dorian scale for your solo there.
Best of luck!
