Announce a transition time a few years into the future so the miners don't get a capital loss. Code clients to switch over to the new algorithm at the transition time. When the transition finally comes, even those with slightly out of date client will switch over, since it was coded far in advance.

Wouldn't this require quantum computing to be developed relatively gradually and in the open? Seems likely that a gov or company will suddenly reveal it or have it exposed.

Sudden, catastrophic leak of an operational QC would definitely be a cryptogeddon scenario.

That's really the problem I foresee. It'd be extremely hard to pull off without a bank run or a speculative frenzy. Financial markets are unbelievably skittish about uncertainties.