I think some of the administrative pain can come from having a 'sandbox' or 'qa' tier beyond dev (which in this case would be customer facing) before production.
If data separation isn't required/essential, seems as though a a separate environment is actually unnecessary and feature gating could be used. But if data separation from other customers is required, then new infrastructure should be introduced via separate CICD if I follow correctly?
Pretty much. It's hard to guess at the reason why without knowing the product, but for whatever reason customers are wanting access to new features/releases before using them. Which likely means that they need to do something on their end every time you release (validation, update internal training/process documentation, etc). And it's causing disruption when things change outside of their control. So they're wanting more control over that change timing, to smooth out the impact of those releases as far as their usage goes.
If your release codebase can only support a single "production" version of a feature at once, you end up having to provision entirely new environments to hold a client back. And again, for every client wanting this. Because the timing they want isn't going to be convenient enough to be the same.
So instead, structure things so that you can run both the old and new version of "the thing" simultaneously in production, and give the client self-service ability to activate the new version when they're ready. That way your production environment itself is able to accommodate these requests and client's can opt-in when they're ready/comfortable to.
The biggest challenge to doing this tends to be architecting your application so you can push releases to the backend independently to releases in the frontend. Which can generally be handled by routing things through middleware that provides a stable response for a given feature version. If the interface is using the latest version, the middleware is basically just a stub that does nothing. But if the interface is using a prior version, then the middleware accepts the request signature of the prior version, translates into what's needed to execute on the new codebase, and returns a response that's consistent with the prior version. It's a few years old, but here's[1] an example of how we handled the data-model aspect of this sort of setup at a prior company
So in effect you're actually upgrading all customers to the new release at once, but from the customer perspective everything still looks/feels/act the same as they're used to until they "upgrade/opt-in" to the new release.
It's a pretty major lift to implement this architecture (particularly on an existing codebase), but maintaining it is easy to incorporate into the regular development process. And completely eliminates the operational and customer management headaches you're having now.
With this architecture, it doesn't really matter if you're running isolated deployments or a multi-tenant architecture. You only ever have a single version of production in both cases. The "sandbox" isn't a new environment, but a new production account that copies over the configuration/setup of their existing one while applying sandbox-like restrictions to it. This gives them a temporary space to prepare for the change so they're prepared when they flip the switch on their primary account.