Would a post-naturalization name change require a new naturalization certificate? All these horror stories are pushing me to reconsider doing a judicial oath, so I'm wondering if the naturalization certificate would still be valid.
You do not need new nat cert after name change. (You can order one but it costs like 400$ and takes a year, based on what USCIS website says for replacement certificate.)
Your nat cert and name change order from court together gets you US passport with new name. Your passport is also the proof of US citizenship and once you have passport in correct name, you do not need nat cert anywhere. Anywhere you have to show citizenship proof, you can use passport.
If somebody asks for nat cert, take both nat cert and name change order and they both together satisfy the requirement.