Why is Set, and not Rel, so ubiquitous in mathematics?

Regarding question 3, one can make an argument that actually the fundamental object is "Set together with Rel". The bijective-on-objects inclusion of Set into Rel is a categorical structure that can be expressed as an F-category, a proarrow equipment, or a double category. All of these are slightly different ways of talking about a (2-)category that has two classes of morphisms.

It turns out that in the particular case of Set+Rel, either class of morphisms can be recovered from the other. The relations are the jointly monic spans of functions, while the functions are the relations with right adjoints. The same fact holds in much greater generality: from any regular category (whose morphisms are "function-like") we can construct a unitary tabular allegory (whose morphisms are "relation-like"), and conversely. The two are really just the same structure expressed in different ways. Sometimes it's more convenient to use the functions; sometimes it's more convenient to use the relations; and sometimes we want both encapsulated in a single structure.

The importance of this sort of two-kinds-of-morphism structure becomes more pronounced as you go up in categorical dimension. For instance, the analogous thing for categories is the inclusion of Cat (whose morphisms are functors) into Prof (whose morphisms are profunctors). In this case, Prof can be constructed from Cat, but with rather more difficulty than Rel is constructed from Set, while Cat cannot be recovered 2-categorically from Prof (e.g. Morita-equivalent categories are equivalent in Prof, but not in Cat). On the other hand, profunctors seem an essential ingredient for doing "formal category theory", e.g. in the formulation of weighted limits and colimits, so it's valuable to keep both kinds of morphism around.

Taking up remarks near the end of the OP, and somewhat in line with Mike Shulman's answer, I'd like to underline the structural interplay between $\mathbf{Set}$ and $\mathbf{Rel}$ to indicate one point of entry into the notion of topos.

• The bijective-on-objects inclusion $i: \mathbf{Set} \to \mathbf{Rel}$ has a right adjoint $p: \mathbf{Rel} \to \mathbf{Set}$.

This means that there is a natural bijective correspondence between relations $iA \nrightarrow B$ and functions $A \to pB$. Here $pB$ is of course the power set of $B$.

Quite a lot of fundamental structure comes out of this. For example, the counit of the adjunction is the elementhood relation $\ni_A: ipA \nrightarrow A$. The unit of the adjunction $A \to piA$ is the singleton function $a \mapsto \{a\}$. The multiplication of the monad $pi$ with components $\mu_A: pipiA \to piA$ is the function $\bigcup_A:ppA \to pA$, taking a collection of subsets $\mathcal{A} \in ppA$ to the union $\bigcup \mathcal{A} \in pA$.

Yes, as the OP quoted Wikipedia:

• $\mathbf{Rel}$ is "just" the Kleisli category (of free algebras) of the monad $pi: \mathbf{Set} \to \mathbf{Set}$.

But turnabout is fair play:

• $\mathbf{Set}$ is "just" the Eilenberg-Moore category (of coalgebras) of the comonad $ip: \mathbf{Rel} \to \mathbf{Rel}$.

I find it hard to play favorites between $\mathbf{Rel}$ and $\mathbf{Set}$, because of this structural interpenetration between the two. You might prefer $\mathbf{Set}$ because it is complete and cocomplete. On the other hand, you might prefer $\mathbf{Rel}$ because of its self-duality ($\mathbf{Set}$ breaks the symmetry enjoyed by $\mathbf{Rel}$), and because $\mathbf{Rel}$ enjoys a richer structure of honest 2-category (whose 2-cells are inclusions between relations of the same type $A \nrightarrow B$). It's probably best to see them welded into a whole, as a certain type of double bicategory as in Mike's answer.

Now let me use these ideas to give a snappy definition of topos. As many readers will know, the notion of regular category $C$ is useful because (among other things) it allows a decent calculus of relations. Thus from a regular category we may form a category of internal relations in $C$, denoted $\mathbf{Rel}(C)$. Again there is a bijective-on-objects inclusion $i: C \to \mathbf{Rel}(C)$.

• Definition: A topos is a regular category $C$ such that the inclusion $i$ has a right adjoint $p$.

2) The definition of "homomorphic relation" for groups in the question only refers to the multiplication, but it is more natural also to require compatibility with inverses (because we are not talking about semigroups which happen to be groups, but about groups; although it is well-known that the forgetful functor is fully faithful, i.e. the homomorphisms are the same, this is not the case for the "homomorphic relations"). Then homomorphic relations $R$ on a group correspond 1:1 to normal subgroups $N$ of the group (via $(x,y) \in R \Leftrightarrow x y^{-1} \in N$). More generally, a congruence relation on an algebraic structure is an equivalence relation on the underlying set which is compatible with all the operations. Equivalently, the quotient of the underlying sets becomes an algebraic structure of the same signature such that the projection becomes a homomorphism. The homomorphism theorem holds in this general setting. I hope that this refutes the claim that we never see homomorphic relations.

3) The Yoneda Lemma holds for enriched categories over symmetric monoidal closed categories, and $\mathsf{Rel}$ is a symmetric monoidal closed category, with tensor product coinciding with the cartesian product in $\mathsf{Set}$ (this is not the cartesian product in $\mathsf{Rel}$, which coincides with the coproduct in $\mathsf{Set}$).

Note that $\mathsf{Set}$ has many more convenient properties than $\mathsf{Rel}$. For example, Milius' paper On Colimits in Categories of Relations explains that $\mathsf{Rel}$ has not all colimits of $\omega$-chains.