Entweder ich oder sie
In English, we can say eg "Either he or I can go with you" or "You can go with either me or him." That is, the pronouns used depend on whether "either.. or" forms the subject or the object. Is it the same in German? "Entweder ich oder er" if its the subject and "entweder mich oder ihn" for the object?
Either you can go to a movie with me or you can go to dinner with him.
Either I can go to a movie with you or he can go to dinner with you.
The only difference between these and your examples is that you're also choosing between two different activities. But if you substitute going to a movie for going to dinner in the second half, you're back to just choosing between individuals. Then the sentences can be shortened:
You can go to a movie with either me or him.
Either he or I can go to a movie with you.
So, yeah, since both pronouns are playing the same role, they have to match.
Same is true in German. You just have to think about what's implied but not said.