How would a hard fork for a new key-pair/address generation algorithm be implemented practically?
You'd have both the old and new address types valid. You can't drop support for the old address types because there's no guarantee all coin users are going to convert their coins right away.
The updated wallet software, merchant services, etc will all only provide addresses in the new format though, so eventually the use of the old addresses will slowly drop off, just like how with the adoption of segwit, legacy address use dropped off (although not completely phased out).