I am hoping to start a grad program in one of those medium cost-of-living cities, and have been doing lots of research. Since it sounds like I'm more familiar with the US than you, I'll give you what I've learned.
This will of course depend on your standard of living. I assume because you are married, you would like to live in your own apartment/house and not live in one bedroom in a four-bedroom house. This answer is based on that.
As another caveat, I would say I'm moving from a very expensive area, so it's possible I'm overestimating other expenses based on my experience here.
At more than $30k (the value of some awards), I feel like I could minimally support myself and my wife (who is also going back to school). We also have a nice chunk of savings that we've been accruing for two years that helps me feel better about living on the stipend.
At less than that, around $25k, we would plan on my wife working 8-12 hours a week to supplement my income.
Those numbers are totally unlivable in high cost-of-living areas, like where I live now. I couldn't imagine trying to live here on less than $50k combined; and that's a totally unachievable PhD stipend.
< $20k - Not a chance, would expect my partner to work at least part
$20-25k - Doable, with decent savings and a few hours of work on your partner's side.
$25-32k - Much more doable, but still tight living
>$35k - As comfortable as you can be on a PhD stipend.