Sliding at a quasi-statically loaded frictional interface can occur via macroscopic slip events, which nucleate locally before propagating as rupture fronts very similar to fracture. We introduce a microscopic model of a frictional interface that includes asperity-level disorder, elastic interaction between local slip events, and inertia. For a perfectly flat and homogeneously loaded interface, we find that slip is nucleated by avalanches of asperity detachments of extension larger than a critical radius A(c) governed by a Griffith criterion. We find that after slip, the density of asperities at a local distance to yielding x(sigma) presents a pseudogap P(x(sigma)) similar to(x(sigma))(theta), where theta is a nonuniversal exponent that depends on the statistics of the disorder. This result makes a link between friction and the plasticity of amorphous materials where a pseudogap is also present. For friction, we find that a consequence is that stick-slip is an extremely slowly decaying finite-size effect, while the slip nucleation radius A(c) diverges as a theta-dependent power law of the system size. We discuss how these predictions can be tested experimentally.