Okay, game rolls tonight.
Thanks everyone for all the awesome suggestions. Really got my brain working.
So here's the scoop. The king of the Wind nation, Huitzilpochtli, has been receiving guidance in his dreams telling him to send She Who Seeks The Lost Child into the Hidden Storm of Flame and to take what she finds to the Sun Disk in Tehuatcan. The problem is that the Hidden Storm of Flame is a taboo site to the Wind, and She Who Seeks The Lost Child is a barbarian, and for the Wind to accept assistance from a barbarian would be a very great pollution, especially if they're sending her into a taboo site.
He knows that She is in this caravan, so he's brought his entire nation here to take her. His plan is to have one of the barbarians (remember, to him, the PCs are barbarians) fight his great champion. If they win, the nation will accept their assistance because obviously anyone who can defeat the champion of the Wind is blessed by the gods. If they lose, they'll be his slaves and he can have them do whatever he likes.
She Who Seeks The Lost Child refers to one of the PCs, who received a vision of her deceased daughter asking her to journey into the underworld to retrieve an artifact. The Hidden Storm of Flame is a recent meteorite impact -- Barsoom is being bombarded with meteorites suddenly, big ones that are destroying whole chunks of the world. What our heroes don't yet know (but kind of suspect) is that these meteorites are actually sorcerous artifacts that will call back the old, banished gods of Barsoom.
Which would be, in Igon's words, "Bad."
So the challenge against the Wind champion will be a pole fight. Not a fight with poles, but a fight ON poles. The chosen champion from each side will have to balance on the top of a 40' high pole and fight without falling. The rest of the group hold the pole upright, so they can try and help out with Str checks (though they run the risk of overcompensating).
Oh, and the Wind champion is a blade dancer (OA) with like a +43 Balance check.
So the PLAN is, fight the champion, jaw things over with Huitilpochtli, head into the Hidden Storm of Flame and confront the secret of the old gods' meteorite. My PCs of course are notoriously good at defeating my efforts at planning, so we'll see what happens.
Thanks again, everyone. I think we're gonna have fun.