What is "flyover country"? There's a world of difference between a place like Chicago or Minneapolis (an underrated gem) and some exurb in the Deep South. Does Chicago count as "flyover country"? You can definitely get the kinds of people they're looking for to move to, say, Chicago or Minneapolis. A suburb 40 miles from Chicago, on the other hand, is pretty much a doomed location.
Being in a city (even a mid-sized city like Madison) matters more than the general geographic area. Chicago itself is rock-solid, an office park near the airport is not going to work.
* Obviously, if you're not paying a full relocation package (which includes a month or two of temporary housing, all moving costs, and a spousal placement agency) then you're not playing to win, and you won't.
* Same pay as on the coasts. Excepting Chicago and Minneapolis, you may even want to make that 110 to 120 percent in order to offset decrease of spousal pay.
* 3-5 conferences per year, fully paid. Announce it upfront as a perk.
* Establish a culture of giving back to the open-source world. Get the names of some star employees out there. People will then apply in order to work with them.
* At least 4 weeks of vacation. Minneapolis is beautiful, and its winters aren't as bad as people make them out to be, but getting out of there for a week or two in February really helps.
* Enough interesting work, and enough diversity of interesting work, that the job looks like a probable 3-5+ year fit. If it's run by McKinseys, you're dead in the water. Great engineers want to work in engineer-driven companies. Cross-country moves are too stressful to do one without an assurance that there'll be interesting work to do many years out.
* Culture of talent development and internal promotion. This needs to be verbalized in recruiting. "We're in <X>, so we invest in talent. We can't take smart people for granted." Now it's a selling point.
* Remote work. Smart people want to work with other smart people, and while you'll have some rock-solid people who are willing to move, you won't get "critical mass" unless you allow remote work.