Just to pile on late, I would add to this. To meet the "interesting" part, you may be able to extend it to a National Laboratory, which is a bit quasi-government.

The academia route certainly exists, but the glut of of PhDs compared to available positions combined with the amount of complaining I've heard from non-tenured professors would make me a bit hesitant to advocate this route as a general recommendation. But there are other staff positions that might better fit that bill

Seconded (I’m in academia, my wife is in government).