I am writing a letter to my boss and my senior.
Dear Mr. John and Mrs. Jane,
I feel it's a bit weird because they are not couple/married.
Does it sound normal to write like that?
First of all, please note that the usage "Mr. Firstname" or "Miss Firstname", as in your example, are conventional only in specific subcultures of English speakers; I encountered it for the first time when I was working with prison inmates. (I am unaware of any community of English speakers that would utter "Mrs. Firstname".)
Properly speaking, which is to say in formal English, "Mr" and "Ms" (and "Miss" and "Mrs") are all applied to last names, or full names. So "Mr. Smith" is fine. "Mr. John Smith" is fine. "Mr. John" is really weird unless you are in some parts of the American South, and even then, I'm not sure you'd address a letter that way in a business context.
Second of all, part of why it feels weird is that in your example you address a woman as "Mrs." At least in the US, one does not ever address a woman as "Mrs." in a business context unless she has specifically indicated that it's her preferred title (same rules as "Capt." and "Rev.") precisely because it refers to her marital status. The reason it feels weird to address a man and a woman that way when they're not married is that the "Mrs" title is explicitly making a comment about her being married. That is why using "Mrs." is considered gauche in the workplace. Same with "Miss".
The professional default title one uses for a woman is "Ms." and she is addressed "Madam" (parallel to "Mr."/"Sir"). You may find that
Dear Mr. Wu and Ms. Smith
feels a lot less weird.
Should you find yourself needing to use "Mrs." (say, in a social context, like writing wedding invitations), there's a whole archaic set of rules for its correct use, about which I am very hazy. (Something like if Jane Doe marries John Smith, she's Mrs. John Smith but not Mrs. Jane Smith? I remember it was non-obvious and complicated.) Refer to an etiquette manual.
Frankly, the correct rules for deploying "Mrs." were complicated enough, that was what drove the widespread adoption of "Ms." which works just like "Mr."
It depends on the communications culture in your business. I work for a large multi-national but we have a 'first names' culture. Even when writing to my CEO I use their first name.
When I need to write to more than one person I tend to put the names of the people I am directly communicating with first, then those I am keeping informed.
So, for my circumstances, the letter would simply start
Dear John and Jane
As Codeswitcher explained it would be unusual to include a title with a first name. Avoiding them also means you don't have to worry about the correct form of address.