Yeah, it's a one-or-the-other fight. Both join you either way. But, c'mon, why wouldn't you do the Psychic land first? I mean, their army has the lower Strength rating. >.>
Just remember to hunt down the two Warlords serving with whichever leader you don't fight. While the main warlord of the city will join you, his two majordomos will start wandering the other cities.