When I've seen that "your password is too similar..." warning, it was with a system that required entering my current password to set a new password, so no need to store a previous version in plaintext.

Though another way around it is to apply a set of common transformations to your new password, hash it and see if it matches the previous one. I.e. if your current password is "Password123" and you try to set it to "Password1234", the system could truncate the last digit on the new password and see if it matches the current one.

I think almost every system requires you to put in your current password to change new password.

Aren't passwords hashed on the client side before sending it across the network? That would make your way around not work (unless that's done on the client side also after verifying from the server that it's correct).

Hashing it on the client side will make the hash the password. So the stored hash can be used as password by turning off the client side hashing, for instance by turning off javascript. You use https to avoid sending the password in cleartext over the network

I've certainly never encountered a web app that hashes locally before sending. I suppose it could work if this was at the account creation or password management stages, but you couldn't implement it at the login stage for obvious reasons.

I'm having trouble imagining what scenario client-side hashing would protect against.

Man in the middle attacks fetching for plaintext passwords

-- edit: using a KDF would improve it even more.

If the client only sends the hash to the server, a MitM also only needs to capture the hash.

Sure, but if they've MITM:ed your trusted certs, aren't you already boned in so many ways?