I've read elsewhere that the only option in my scenario is to create a new contact and delete the old one.

From when I last checked a year or so ago, this still holds true. This is how I've implemented it in my application.

OK, so first I need the contact ID. Apparently the only way to obtain this (if you don't already have it) is to use the search by email endpoint

This is also true. Additionally, take into account that contact creation is an asynchronous process that may take several minutes to complete, so the contact ID is not immediately available after creation. Other operations such as adding a contact to a list may also have a delay of seconds or minutes to be visible to subsequent "GET"-type requests.

Am I forced to additionally determine which unsubscribe groups the original contact belonged to and replicate their unsubscribes?

I'm afraid so, yes. I would also check if a deleted contact's email address is also removed from a Global or Group unsubscribe list. It may just as well remain, which is probably not an immediate problem for you, but it might cause an unexpected situation if the user re-subscribes on the new email and then reverts to the old email and has their emails blocked (admittedly fairly unlikely).

I mostly don't use Unsubscribe Groups. I use list membership to denote whether a contact is subscribed or not. If they unsubscribe, I remove them from the list. This may also be an option for you, but I'm running into other challenges here due to the intervals in which segments update based on list membership. Unsubscribe Groups are probably more reliable.

This whole process seems so badly designed for what must be an extremely common scenario so I'm hoping someone out there can tell me what I'm missing.

I agree that this developer experience is horrific. You're not alone in this feeling. I don't think you're missing anything though.