RC, thanks for the added details.
In general terms, it sounds like you have three people who get along and are interested in maintaining stable and healthy relationships. That's a pretty good start.
Right now, IMHO, you have two things going on: NRE and what I call PAS (Poly-Adjustment Syndrome). The NRE will eventually level out, and dealing with that is usually just a matter of time. You may even find that the total relationship energy is higher after equilibrium. Right now it'll feel skewed, but relax and float over the ripples, and you'll ride it out fine.
PAS is something that I see when people transition from mono to poly, and it sounds like your situation fits that bill. Often the more mono person in that scenario feels abandoned by the poly person and fears a loss of the original relationship. Even when reassured that the original relationship is safe, there is a lingering fear that the original relationship will be changed in a way that in unacceptable.
In all reality, sometimes this does happen. However, your reactions and other details in your particular story lead me to believe that you will be ok. She isn't the only one going through change. She's wrestling with how this new man fits in your life, but so are you. That means growing pains for everyone. The fact that you respect this other guy, the fact you've mutually reaffirmed your marriage, and the fact the guy has expressed respect for your marriage are good signs. The thing about PAS is that the fear of what could happen is almost always worse in our minds.
I'm actually not surprised they didn't talk about falling in love even after they knew it was happening. How long has it been since your wife fell in love with someone new? It may have been something they weren't expecting or they weren't sure what the feelings were. Sometimes people realize it's love long after it's obvious to others. And really, your wife as someone who a guy could totally fall in love with? You of all people should know that she's someone who lovable. If I were you, I'd try not to think of their delay as "they lied to me" but think of it instead as "they were struggling with categorizing their feelings and when and how to tell me." It had to be pretty intimidating for a wife of almost 20 years to come to her husband and say she loves another man, right? Wouldn't that be something you'd wrestle with if the table were turned?
One of the basic tenets I belive in as a poly person is that the heart grows larger as you learn to love. Your wife falling in love means her total capacity for love has increased, not that she is taking love from you for him. Think of when you had kids. Did she not love them? Ridiculous. She loves them, and she loves you as much or more after them, yes? (This children and the growth of love theory is actually how I started down the road to poly myself.) Loving the kids, loving the other guy, these don't diminsh the 20 years of love she has for you.
What doesn't grow is the number of hours in the day. Time management is very important in poly situations. In your case, there are large periods of time where the wife wanted a companion, but you were providing for the family. There's a simple spot for new guy to fit in that fills that need but doesn't impact the time you have available. As for overlapping time, let the NRE dissipate, and then work on that.
My suggestion: encourage her to make the connection between you and other guy. Let her do that because she has expressed the desire and because she's trying to set it up so it'll be ok for her men. (She's caring about how you see each other.) Sooner would be better than later because the sooner you each become tangible people, the sooner the boogeymen go away.
You might even sit her down and ask her straight out the things that you could do that would make things easier on her so she can explore stuff with him. I'm thinking stuff like watch the kids or take care of things around the house to free her time up. You might find that actively promoting her endeavor helps you feel more included and reminds her just how awesome a husband you are.
Let me finish by reiterating these words from Carma:
"Love has lots of dimensions. I've found that exploring them isn't as dangerous as I used to think."