What's the name of the external service you're referring to? If it's actually a base url, "named credential" might be a better option. It'll abstract the base url for you, and if you need to offer authentication or a certificate, it'll do so...
If that fails, custom metadata could be a bad idea. You can add more (but not from apex) but if you deploy using Git/Ant/SFDX CLI instead of changesets, it'll be a nuisance because you'll require distinct custom metadata values for sandbox and production. It sort of ruins the purpose.
You might be better off utilising custom settings (hierarchy is enabled by default, but list requires a checkbox to be flipped in setup).
You can also change them using Apex. In an ideal world, you'd have a "postcopy" class that runs as soon as the sandbox is refreshed, overwriting the custom setting with the non-prod value. I don't think you can do it with named credentials; you'd need a tiny deployment or a manual step.