Almost by definition, different syntactic theories should not explain why many native English speakers find "him and me" more natural, because syntactic theories are about the principles underlying a person's ability to produce and understand utterances, and not about their attitude towards utterances. Sociolinguistics is about attitude, caused by social facts. There could be a well-defined sub-area of sociolinguistics, analogous to sociophonetics (i.e. sociosyntax) which uses the devices of a syntactic theory to account for attitudes (I don't know if there yet is such a sub-area). Syntactic theory simply accepts that some people's grammars generate one pattern, and some people's grammars generate a different pattern, and it gives you the tools to talk about each pattern.
Variation is "the big problem" in the study of grammar. There is a tendency to treat all variation as essentially the same, but that is clearly mistaken – there is individual variation, and social variation. Social variation is where a person says something about English which turns out to be true of American English but not Indian English. Individual variation is where a single individual allows more than one output: individual variation is the interesting kind of variation from the perspective of grammatical theory. If I tell you that English and Norwegian differ in some way, you probably wouldn't find that to be a kind of "variation", yet because various different languages are called "English", we have a hard time accepting that people in Newcastle speak a different though related language from people in Seattle.
Individuals have the ability to adjust their linguistic behavior especially when repeatedly exposed to other dialects, therefore I might actually say, sometime, that "I and a bunch of others are going to the pub", which is clearly forced linguistic retraining due to the school system. My revulsion for "I" in a conjunction is strong, greater than that for "he, she, they" ("he and you should get together" is okay-ish, though "him and you should get together" is better). I guess there must be others who are more accepting of the normative dialect.
If we set aside the problem of how to dispose of individual variation, we can certainly ask "what structural facts determine this pattern of pronouns". We can also change the pattern and ask "What differentiates pattern A from pattern B?". Here is a table of pertinent combinations in subject position (no judgment attached).
1 He is leaving soon.
2 I am leaving soon.
3 Me is/am leaving soon
4 Him is leaving soon
5 Him and me are leaving soon.
6 Him and I are leaving soon.
7 Me and him are leaving soon.
8 Me and he are leaving soon.
9 He and I are leaving soon.
10 He and me are leaving soon.
11 I and he are leaving soon.
12 I and him are leaving soon.
Some of these are complete gibberish, some are perfectly natural, and some are questionable. You decide.
3,4 are utterly ungrammatical; 1,2 are wonderful. 5 is the best conjunction, followed by 7 but I know the rule that I was told which forces that order. 11 and 12 are the worst of the conjunctions. 6,8,9,10 are hard to sort but I'd say that 6 is better than 9; 8 is the worst of those 4.
I left out from the paradigm of inversions structures like "Are {he and I; me and him; him and me...} supposed to go soon". Also considering how terrible it is to put "I" or "he" in object position (conjoined or otherwise), and considering the fact that the natural 1-word (pronoun) answer to a question "Who Verbed X?" is "me, him, her, them" and never "I, he, she, they", I conclude that "I, he, she, they" are only used in subject position. You get the "I am leaving" / "Me and him are leaving" difference by appeal to the syntactic notion of C-command. In some (less-flat) theories of syntax, the tendency to use the unmarked pronoun form increases when the pronoun is structurally further from the following verb.
So this is a question that is eminently addressable by syntactic theory, as long as you only ask for the structural correlates of a pattern. Non-syntactic theory may explain the motivation for the arrangement of preferences, for example
the reason why "me and him" is dispreferred is that I was told as a child that it makes people think that he is mean.