This ended up being due to a global invocable action being included in a managed package that we no longer subscribed to (for us, it was TaskRay). This will happen with any license restricted managed package with invocable actions. Additionally, the issue will only show itself in a production instance since licenses aren't managed in a sandbox.
Salesforce published a knowledge article to explain but has not, as far as I know, published a known issue. Knowledge Article:
Description
When opening a flow, you may encounter an error message that says:
"Error: Can’t load invocable actions"
Resolution
The error shows up when you open an existing visual flow or when you create a new flow because all invocable actions available in the organization will be loaded in the cloud flow designer palette. Even though they're not referenced in the flow, they'll still be loaded. To resolve the issue, you'll need to extend the license of the managed package or delete the expired package.