The issue is the version of macOS the recovery is trying to install as well as the systems firmware level if you where running Sierra or older.
So… the easiest way is to prep up a 32GB USB thumb drive using the recovery service, then upgrading it to Mojave or newer via the Apple Store, then just run disk Utility from the thumb drive you should see it at that point both the version of macOS will be the correct version and the systems firmware will have been upgraded.