"Surprising" categorical equivalences This is inspired by this question about the equivalence between the category of finite sets and non-negative integers. Now this question was (rightly, I guess) closed, but the fact was surprising to the OPer. I didn't know about this, but it was easy to verify. I had a little bit of difficulty understanding the nuances between categorical equivalences and category isomorphism until I thought about the analogy with homotopic spaces and homeomorphic spaces.
I was wondering about other equivalences that might unexpected and/or not so straightforward to prove. I would appreciate answers to a general audience...things that a beginner or an expert might find of interest.
 A: The tangle category $\text{Tang}$ is the category whose objects are the non-negative integers $n$ and whose morphisms $n \to m$ are collections of paths from $n$ points arranged on a line in $\mathbb{R}^3$ to $m$ points on another line in $\mathbb{R}^3$ up to ambient isotopy, possibly with some links thrown in. Composition is given by connecting the paths together. In particular, $\text{Hom}(0, 0)$ consists of links in $\mathbb{R}^3$.
$\text{Tang}$ is a monoidal category with the monoidal operation given by disjoint union. It is also braided monoidal with braiding given by the obvious geometric move. Finally, it has duals given by flipping morphisms upside-down, and every object is self-dual. Note that the core of $\text{Tang}$ is the braid category. 
Theorem: $\text{Tang}$ is the free braided monoidal category with duals on one self-dual, unframed object.
This fact, and others like it, have some remarkable consequences. For example, they allow us to write down knot and link invariants from braided monoidal categories, prominent examples including the categories of representations of quantum groups; the Jones polynomial arises in this way from the category of representations of $\mathcal{U}_q(\mathfrak{sl}_2)$. There is a fairly thorough exposition in Kassel's Quantum Groups. 
A: The $2$-cobordism category $2\text{Cob}$ is the category whose objects are (compact, oriented) $1$-manifolds and whose morphisms $M \to N$ are (compact, oriented) $2$-manifolds with boundary $M \sqcup N$ in the appropriate orientation up to relative homeomorphism, with composition given by identifying the appropriate parts of the boundary. 
$2\text{Cob}$ is symmetric monoidal with the monoidal operation given by disjoint union. But in fact much more is true.
Theorem: $2\text{Cob}$ is the free symmetric monoidal category on a commutative Frobenius object.
In other words, symmetric (strong?) monoidal functors $2\text{Cob} \to M$, where $M$ is a symmetric monoidal category are the same as commutative Frobenius algebras in $M$. 
I always thought this one was particularly funny because the original motivation for the definition of a Frobenius algebra has nothing to do with topology. This is a very special case of the cobordism hypothesis in TQFT and is explained carefully with lots of pictures in Kock's Frobenius algebras and 2D topological quantum field theories. 
A: Martin already mentioned one facet of Stone duality, but I thought I would mention another, which is equally surprising to me.  The pro-completion of a category is obtained by formally adjoining cofiltered limits (or equivalently, codirected limits).  That is, an object of Pro(C) is a cofiltered diagram in C, with morphisms defined in an appropriate way.  Pro(C) can be identified with a full subcategory of $[C,\mathrm{Set}]^{\mathrm{op}}$ (which is the free completion of C under all small limits).  Part of Stone duality says that the category Pro(FinSet), the result of formally adjoining cofiltered limits to the category of finite sets, is equivalent to a full subcategory of Top, namely the zero-dimensional compact Hausdorff spaces.
A: The category of AF $C^*$-algebras is equivalent to that of ordered abelian groups with strong unit (i.e. an element with the archimedian property, adding this one to itself often enough you can always obtain something bigger than any given element) via the $K_0$-functor. The morphisms in this category are the order preserving, unit preserving group homomorphisms. The latter category is equivalent to the category of MV-algebras via the functor plucking out the "interval" between the neutral element and the strong unit (see e.g. this book).
A: I was pretty shocked by this one: if $V$ is the additive group of a finite-dimensional vector space over a $p$-adic field, the category of smooth (sometimes called algebraic or discrete) complex representations of $V$ is equivalent to the category of sheaves of complex vector spaces on the Pontryagin dual of $V$.
More generally, this is true of any Hausdorff, locally compact, and totally disconnected abelian group which is a filtered union of its compact open subgroups.
A: I can remember twice that I have been really stunned by an equivalence of categories.
First, let R be a not necessarily commutative ring. The category of (left) R-modules is equivalent to the category of (left) modules over the ring of $n\times n$ matrices with entries in R. (This is the simplest example of a Morita equivalence.) I mean, the rings themselves look very different from each other.
The second is that the homotopy category of simplicial sets is equivalent to the homotopy category of CW-complexes. The former is defined purely combinatorially, and the latter is defined topologically: a CW complex is after all defined by gluing together open balls in $\mathbf R^n$ (albeit in a complicated way) and the equivalence relation on arrows given by homotopy is defined by taking products with the open interval [0,1]. It really is remarkable how the process of passing to homotopy can strip away all this topological structure.
A: It's rather subjective what is surprising or not. But there are lots of nontrivial and interesting equivalences of categories. Actually a big part of mathematics is about establishing these equivalences. Some examples:


*

*The category of smooth projective curves over $k$ (alg. closed field) is anti-equivalent to the category of finitely generated field extensions of $k$ of transcendence degree $1$.

*If $X$ is a nice pointed space with fundamental group $G$, then the category of coverings of $X$ is equivalent to the orbit category of $G$.

*The category of locally compact hausdorff spaces is anti-equivalent to the category of commutative $C^*$-algebras. Similarily, replacing $\mathbb{C}$ by $\mathbb{F}_2$, the category of locally compact totally disconnected hausdorff spaces is anti-equivalent to the category of boolean rings. See also Johnstones book Stone duality for more background.

*Tannaka duality, see for example this MO discussion.

*Pontrjagin duality establishes an equivalence between the category of locally compact abelian groups and its opposite category. This restricts to an anti-equivalence between the category of compact abelian groups and discrete abelian groups!
Remark that in the first four examples, in some sense, geometry is connected with algebra. This not just enables you to argue about geometry with algebra, but also the other way round!
By the way, the equivalence between the category of finite sets and the non-negative integers is not surprising at all. Every category is equivalent to its skeleton, essentially by the definitions. A skeleton is some kind of classification of the objects, and a finite set is classified by its cardinality.
A: What one person finds surprising another person won't, but: 
The category of compact Hausdorff spaces and continuous maps is equivalent to the category of models of an (infinitary) algebraic theory, i.e., a theory given by operations and universally quantified equations. (This theory is unbounded in rank, i.e., there is a proper class of operations that need to be specified.) 
A: The forgetful functor from topological abelian monoids to topological spaces has a left adjoint, the infinite symmetric product $\text{SP}$. The Dold-Thom theorem asserts that if $X$ is a CW-complex, then $H_n(X) \cong \pi_n(\text{SP}(X))$; in other words, the singular homology of $X$ is precisely the homotopy of a "linearized" version of $X$.
If you want to phrase this theorem in a more combinatorial setting, you can replace $X$ with a simplicial set, hence replace $\text{SP}(X)$ with the free simplicial abelian group on $X$. 
Theorem (Dold-Kan): The category of simplicial abelian groups is equivalent to the category of chain complexes concentrated in non-negative degree.
This theorem explains, in a precise sense, why the machinery of homological algebra can describe properties of topological spaces. For me it really explains what a chain complex "is": it's a linearization of a combinatorialization of a topological space. 
