You should consider the following important criteria when picking a KRS:
You will want to choose a KRS that has professional experience in securing your keys. A KRS should use industry standard practices, such as keeping keys in an offline vault, encrypting sensitive information, and having audit-able processes.
Recovery requirements and processes
Each KRS provider will uphold and maintain different sets of recovery requirements and processes. Examples of recovery requirements include email confirmations, phone calls, identity verification via passports / utility bills, notarized letters from a company's board of directors, etc.
You should choose a provider that performs an adequate level of verification prior to recovering your funds.
Given that the primary function of a KRS is serving as a backup, longevity of the service provider is of utmost importance. Although you can access funds using the other 2 keys in the event the KRS goes away, you should be looking for a service provider that is likely to withstand the test of time.