Well, as a Sciences Po graduate myself, I can tell you that they are quite elitist regarding admissions.
Normally, the unspoken rule amongst elitist structures is never to accept below 3.5 GPA for US people (you'll find this explicitly in some company's website, like Godman Sachs etc.). So all good there.
Your University seems to be well-ranked. I say you've got a decent shot, though you might want to know that in France, your degree's origin remains the single most important feature in your CV, even if you have 20 years of work experience.
My bet is, you'll be admitted in one the last positions or something, because they'll choose Oxford / Cambridge / Harvard / Yale as first choices regardless of the other aspects of your personnality. I know, it sucks.
Bear in mind that Joint degrees, where admissions are decided by a collegium composed of both Universities will probably value more your work placements abroad and research and stuff, so I'm only speaking for 100% French programs.
And regarding other universities matching your profile...
Ever thought of the ENA (Ecole Nationale d'Administration) ? It's the most prestigious school our country has. I'm saying that because you seem to want to work in a Public stucture (the ENA is for public careers mostly, but getting into Harvard is a lot easier than the ENA, so... )
P.S. : Assuming the French language is no problem to you, I'd say you will qualify, but barely, even though you sound like a pretty darn nice applicant.
Also, there are 9 IEPs (Institut d'Études Politiques) in France. Paris has a better reputation, but mostly in France. People don't seem to care elsewere, because all are very elitist Grandes Écoles.