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).