At our IdP, I can grant all users in the company access, but will only users who are provisioned in Algolia be able to access it?

Only invited users can access a given Algolia application. Yes, all users will be able to create an account via SSO on Algolia but only the users invited to your application will be able to access it. You can invite users to your application by going to the "Team" page of your Dashboard.