QI have a Destruction in Black on my field, my opponent's leader has 2 defense, and my opponent has this follower on their field. At the start of my main phase, does my opponent lose the game?

AYes, they do.

At the start of your main phase, both abilities will trigger and become pending. When both players control pending abilities, the active player resolves theirs first. In this case, you are the active player, so Destruction in Black would deal 2 damage to your opponent's leader, bringing its defense to 0 and causing your opponent to lose the game before their ability can give them +2 defense.

QIf I have multiple cards with an "At the start of each opponent's main phase" ability triggering, in what order do I resolve them?

AYou may resolve them in any order. When an opponent proceeds to their main phase, all "At the start of each opponent's main phase" abilities are triggered and become pending. Then, you can choose the order in which you resolve the pending abilities.