As someone suggested elsewhere, Xenophon's Anabasis isn't a bad starting inspiration.
Take a multi-ethnic/polyglot mercenary force. Bring them to the very heart of a vast and powerful empire. Put them on the wrong side of a succession crisis in said empire. They suddenly find themselves thousands of miles from home, surrounded by enemies, and needing to work together and fight battle after battle, scrounging for supplies along the way, to survive and reach home.
For mercenaries, treat them as Normal Men - that means four General Proficiencies. If you're going to have a game with lots of people with the same class, don't skimp on the best differentiator ACKS gives you. That being Proficiencies.
I'd recommend starting the PCs at 2nd or even 3rd level, unless you've already got a process in place for replacing them. 1st level characters are too fragile for something that's going to involve regular large-scale combat. Maybe allow them a 1st level henchman as potential backup option as well.
Once you're underway, perhaps drop-ins can play a henchman or merc, depending on how frequently they turn up?