Maybe a dark red frame around removed tags, and a dark green frame around added tags?

Sounds good for consistency with the title and body diffs. It might need to be slightly larger than those to avoid being obscured by the styling of the tag boxes, as some of those already have a red background and red border.

Also, red and green might be an accessibility problem, but that's a separate question, for the whole diff not just the tag section. Consistency will still be an improvement. For now I suspect red and green will not cause a problem because all of the removals are in the left panel and all of the additions are in the right panel, so the colour is not needed to differentiate between additions and removals. If in future we introduce the option of inline diffs where there is just one panel with all the removals and additions in one place, then we'd need to think about whether we need another way of distinguishing them. The strikeout we currently have for removals helps, but isn't ideal for a removed hyphen or a removed 4.