If you already have players picked for your game and have open communication, you could get them involved in the creation process by asking foundation questions and building from their answers. If not, ask yourself the questions and see where it leads.
What kind of service are they enlisted in? Military, Intelligence, Arcane Studies, Politics...
Furthermore, what was their last job? Fending off goblins, gathering intel on a growing revolutionary group, investigating a magic shard that was the only evidence of a demonic portal, negotiating with a local farmstead that was refusing to pay taxes.
Feel free to ask follow-up question: How did the last job turn out? What did you bring to the table for this particular job?
What is the country like? Warring, Artisanal, Peaceful, Wealthy, Poor, Import-heavy, Export-heavy, Slave-Driven, Religious. Have each player pick a tag as and have them explain how the country reflects this description. Or pick four for yourself and do the same.
Example: I pick Slave-Driven. The country flaunts an anti-slavery policy, but corruption in the system has led to a large underground, government-sanctioned slave-labour force that operates as the backbone for the politicians' endeavors.
Who do the players report to within their service (Create an NPC to be their "anchor")? This will likely be where they get their next "adventure" from.
This goes ahead and assumes that the players have already worked with each other by working on a previous mission together. Perhaps or two are new, but it eliminates the "how did we all end up here" dilema and leaves that to be figured out through discussion and table-talk. Based on the city description alone, you should be able to get a feel for areas that can breed adventures. The sort of service they are enlisted in will help generate a plot hook, and the anchor npc acts as a reliable person the players can report back to for aid (just don't make him a deus ex machina or supervillain right from the get go).
If you don't have ideas for a campaign, the best thing to do is adapt several published modules or adventure paths into a proper series of adventures. You can also adapt Pathfinder Society scenarios.
Your idea of "players in service to a country" falls in line with most of the PFS scenarios as they involve Pathfinders going on missions for the various faction leaders from Absalom, Osirion, etc.
Find out what the PCs want. When starting a new campaign, I usually require my players establish a background and motivation for their characters. It gives you a lot more to work with.