Curious what did you move them into from SF? SF is usually treated as this infallible perfect piece of software by non-tech folks, especially those looking to pad their resumes.
Do _you_ know what three easy replacements are? If no, how do you know those people are looking to pad their resumes, did you figure that out from your non-SF conversations?
SF has worked very hard to cultivate that reputation, and at the end of the day they're mostly an overpriced application host. Once you communicate to the stakeholders that what they have in SF is just another application, and not actually "special", the conversations become a lot easier to have. They feel like Salesforce has them over a barrel at renewal time and helping them understand they CAN move makes a lot of conversations happen.
The answer to what have I switched people to is at the end of this post.
One company was using SF as a patient management system because their EMR wasn't set up right. They spent 6 figures a year on SF just to communicate with patients, make and change appointments, send and receive documents, record insurance information, etc. I spend 2 months fixing the EMR and they moved everyone to that, canceled, SF, and saved $200k/yr on SF and another $250k/yr on SF consultants. For a $50m/yr business, that's a lot.
Another was using SF as a ticket system. Those folks we moved to FreshService. $180k down to $15k/yr. From my experience, ticket systems tend to be one of the most common existing applications that get duplicated inside SF. People think they have to build it in SF rather than just linking your apps. There was another company who kept SF for their CRM aspects but we moved them to an external ticket system that linked to SF and cut their SF bill from $550/yr to $270/yr.
Then there have been cases where I'm brought in while in the middle of a development project. One of my favorites was this consulting firm said they could do all these things and integrate their EMR and Salesforce and that they had done it before with their custom middleware. But every month there'd be a new change-order from them where they said certain things weren't possible, and it came with an invoice! They were CHARGING this company to reduce the scope of an approved, signed, paid contract. I jumped in and said, "we're not paying any of these change orders, you don't get to charge us to do less work. You promised all these features, you said your software ALREADY DID them. What's the problem?" Then for two months we went round and round where I was able to offer them methods to do every single feature they said wasn't possible, and then they'd invent another reason they couldn't do it. I said we're done, canceling the contract, not paying any open invoices, not paying the remainder of the invoice, and in exchange I wouldn't recommend we sue them to get back everything we paid so far. Their own lawyer agreed, and we parted ways. They had us sign a Salesforce contract before we even paid them, so we were a year into a 3 years salesforce contract and literally nothing had been built out. By this time it turns out I had a reputation in the salesforce finance department, so it didn't take a lot of arguing to get them to offer a 50% reduction in exchange for paying off the contract immediately and canceling it.
What they get moved to depends on what they actually need. 50% of the time it's not a CRM at all but a more appropriate app like an EMR, ticket system, ERP, scheduling apps, invocing solutions for existing accounting apps, etc.
The rest of the time it'll be to CRMs and marketing tools that already exist, or custom extensions/connectors to their apps or a way to link their apps and a CRM. I've moved folks to Monday, Nutshell, Hubspot (who I don't like either but they're better than SF), a dozen others.
I haven't dealt with a company yet that couldn't move to a cheaper alternative with no loss in functionality. If execs have emotional ties to SF then I can't do anything. I had one client, the sales VP shot down a conversion because he liked being able to say "we run on Salesforce!" Literally. he liked being able to brag they could afford Salesforce. I just left that one alone.
I worked at SugarCRM for years. It's often easier than one suspects once you figured out what a customer pain points are and show them a less burdensome solve. Most businesses do not need the kitchen sink approach of SFDC or SAP, they just have rarely had that demo'd to them.