So I have an idea, but I probably need someone to slap me in the face and tell me why it doesn't work.
The idea is a potential POW softfork. Historically, POW changes need to made in a way where at some block the hash of the blockheader is done by a different algorithm. This results in a hardfork of the new node away from the old node.
How about this:
At some block where consensus is reached, a miner would have to hash the blockheader twice. Once with the original algorithm and again with the new algorithm. The block time is forced by consensus to be lengthened during this period to drive the difficulty of down for the original algorithm. Once the difficulty is at the minimum for the original algorithm, the new rule is that the blockheader must continue to be hashed twice with both algorithms, and difficulty can start to rise for the second algorithm.
So, for the old node that doesn't know about the new algorithm, it continues to see that the blockheader is hashed with the original algorithm (yes, the difficulty is low but it doesn't need to know that the blockheader is hashed twice) and blocks are not allowed from that old node anymore, similar to how only segwit blocks are allowed today. I suppose since total work of multi-algo keeps everyone pointed in the same direction, this may only work well in a multi-algo chain.
ping /u/8bitcoder, /u/nzsquirrell