I tried that with 3 test contacts and lost all of their categories.  I only
want to add/delete/change a specific one.  While I could do a mass category
delete this way, I still have to then bring up each contact to add back the
categories I did not wish to delete.  How do I tell Outlook only to get rid
of the one I don't want?

Why not just select them all, R click, then reassign?

That will add the category, not change existing categories.

To change or delete a category on multiple items, select them, right-click and choose Categories, then change only that one category.