Indeed. We have seen "thinly" staffed starbases before, but that basically meant that they didn't have an extra Captain to spare for JAG duty. OTOH, we have seen outposts with two Lieutenants and nobody else, and DS9 originally could have been more akin to one of those.
I wonder, did O'Brien perhaps get extra points for being a Cardassian War veteran and thus knowing some of the technologies of Terok Nor from the start? That old war seems to have been a fringe phenomenon for Starfleet, with very few people even knowing who the Cardassians are; there might not have been too many commissioned officers with the required alien engineering skills but with sufficiently low rank to be sent to such an unimportant posting (rather than, say, to SF Intelligence assignments).
I always got the impression that the Cardassian/Federation border wars were nothing more than a series of incidents that often involved shooting, but not an all out war like happened in DS9. The Federation, still in pre-Wolf 359 exploration not military role, was focused more on containing the Cardassians than actually stopping them.