We are a medium-sized non profit religious organization and are looking to see what CIVICRM can do for us. We are just looking to speak to other users or organizations our size ($10M budget give or take) to hear about how they use Civi and what their experiences have been like. Is that something you all can offer or direct us to the right folks? We have about 2 million contact records and dont want to dump them in to CIVI if it is going to be unusable because of the sheer size of our database.
since this seems to be a question specifically about 'scaling and performance' there have been some other posts about this type of issue eg
You can also see some stats here: https://stats.civicrm.org/?tab=sites showing more than 150 sites with over 250000 contacts in them.
We, Fuzion, and several other providers will have worked with large datasets. Each site is still a bit 'unique' in terms of where you might need to address performance issues.
Eg using a lot of Smart Groups, or worse parent-child Smart Groups, can definitely slow things down.
There are some internal settings such as for Search Preferences which you can tweak to improve performance, but clearly a fundamental issue is about the server's capabilities.
Welcome to Stack Exchange,
Greenpeace's Central Europe Branch is using CiviCRM and has a similarly sized contact base. As expected a couple of tweaks and adaptions were necessary for the system to run smoothly (such as not using smart groups).
If you are interested, please send me a message and I could connect you with someone there.