If you are looking at small inputs, we can construct deterministic sets. The first 12 primes (primes to 37) suffice for 32-bit inputs; the first 23 primes (to 83) suffice for all 64-bit inputs. Of course we could find more efficient sets just like people have done for Miller-Rabin. These sets are made possible since the Euler pseudoprimes are subsets of the Fermat pseudoprimes to the same base (Pomerance,Selfridge,Wagstaff 1980), so the Feitsma/Galway database of base-2 pseudoprimes lets us quickly find all the base-2 epsps under 2^64.
For crypto use, I think looking at FIPS 186-4 and their suggestions on error bounds, translated from the 4^-k of Miller-Rabin to the 2^-k of Solovay-Strassen, would be worthwhile. Their suggestions are from 2^-80 to 2^-128 for key generation.
Informally, Peter's numbers look reasonable to me.
Miller-Rabin is more efficient and there is a lot more literature about using it. It may be worthwhile to use it instead from a practicality standpoint, but that's an aside.