Hmm. In Golden Sun, those first four would be fire (naturally), water, wind, and earth, respectively (assuming 'nature' mostly means 'plant-based'). I have no idea about spirit damage, though. Which would be the most useful is hard to say; each of these bosses' vulnerability is the other's secondary resistance.

As for armor, yeah, lightning is probably the best bet. Both of them use a lot of lightning-based spells, although they have access to others.