It almost seems like semi-rural areas are a better place to start, as they're less regulated (no "cable monopoly", no NIMBYs) and the properties are too far away to have the options of Cable/DSL.
Verizon's site will say that Fios is available where I used to live in Haymarket VA, but when I call them up and ask for it, they say it was an error on their site.
I landed on this house: <deleted out of respect for the owner>.
This looks pretty rural to me.
Then I went to their telco and the first thing on the homepage was a link to check for fiber availability.
Fiber is available for this home.
You might have to rethink your plan for competition. I'm guessing the result won't be too different for Mississippi, Texas, Ohio, etc.
EDIT: I tried again and landed in Batesville, AR. It seems there are three Fiber ISPs here.
Edited for courtesy to individual property owners.