I propose that people who opt-in to mining the new algorithm receive time-locked coins. Currently the coinbase for finding a block is 10 ZEC that is time-locked for 100 blocks. I propose that for blocks found with the new algorithm, it would instead be 50 timelocked utxos worth 0.2 ZEC each, and each one timelocked for 4000 blocks longer than the previous one.
That way, every miner choosing to mine the new algorithm would be a long-term investor in the value of ZEC and would have an economic incentive to protect the network, regardless of whether they were mining with ASIC, GPU, CPU, or something else.
This addresses the issue of “loyalty” that you mentioned in your comment.