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$.