Go for 105C (or better) if it'll fit. Doesn't generally hurt to overspec the voltage for longevity reasons as well.
As for tolerance, the "ideal" option is somewhat dependent on the usage. +/-20% is usually OK. For bulk smoothing caps, +80/-20% is usually OK. Of course, going tighter is never a problem.