HI there. There is no minimal installation of Exchange 2016, all the roles are combined into the mailbox role essentially.
https://learn.microsoft.com/en-us/exchange/server-roles#exchange-2016-hybrid-deployment
You would need to bring up a new server as you mentioned and move all and any mailboxes to the new server including the system mailboxes:
Get-Mailbox -Arbitration | New-MoveRequest -TargetDatabase <NewDB>
Dont forget the audit mailbox:
After that, ensure the new server has connectivity to Exchange Online through the firewall (ports 443 and 25) ( Matching what you have now)
then re-run the Hybrid Wizard using the new server as the endpoint.
/Mode:RecoverServer does not apply here since you are building a new server.
Once the new server is up and running and working, then remove Exchange from the current server from the Add/remove Programs dialog menu...