I don’t think Truman State has been mentioned yet. It’s Missouri’s public honors LAC, and it attracts a lot of strong students who can’t or don’t want to overspend on a rigorous education. https://www.truman.edu/majors-programs/majors-minors/political-science-major/ You’d get their maximum auto-merit, so your worst-case COA there would be 26K/year; but there are also competitive scholarships that could lower it more: https://www.truman.edu/admission-cost/cost-aid/scholarships/competitive-scholarships/
I have no idea whether this would be a fit for you, but the Coast Guard Academy has an IR concentration within its Government major Government - United States Coast Guard Academy and would of course be free, with a service commitment. Unlike the other service academies, it has a more typical admissions process.