Small simplicial complexes with torsion in their homology? Fix a prime $p$.  What is the smallest integer $n$ so that there is a simplicial complex on $n$ vertices with $p$-torsion in its homology?
For example, when $p=2$, there is a complex with 6 vertices (the minimal triangulation of the real projective plane) with 2-torsion in its homology.  I'm pretty sure that it's the smallest possible: with 5 or fewer vertices, there should be no torsion at all.  When $p=3$, there is a complex with 9 vertices (a triangulation of the mod 3 Moore space, for instance) with 3-torsion.  Is there one with 8 vertices?  With $p=5$, there is a complex with 11 vertices, found by randomly testing such complexes on my computer.
We can refine this: fix $p$ and also a positive integer $d$.  What's the smallest $n$ so that there is a simplicial complex $K$ on $n$ vertices with $p$-torsion in $H_d(K)$?  Or we can turn it around: for fixed $n$, what kinds of torsion can there be in a simplicial complex on $n$ vertices?
(A paper by Soulé ("Perfect forms and the Vandiver conjecture") quotes a result by Gabber which leads to a bound on the size of the torsion for a fixed number $n$ of vertices; however, this bound is far from optimal, at least for small $n$.)
 A: Gil Kalai has a beautiful paper from 1983 where he shows that, on average, $\mathbb{Q}$-acyclic $d$-dimensional simplicial complexes $S$ with complete $(d-1)$-skeleton on $n$ vertices have
$$| H_{d-1}(S, \mathbb{Z}) | \ge \exp (c n^d) $$ for some constant $c > 0$ depending only on $d$ and not on $n$.
These results are for the total size of the torsion group, and not for $p$-torsion specifically.  But for $d=2$ this at least gives that torsion group can grow exponentially in $n^2$, rather than in $n$.
Now the more speculative part.  My best guess for the structure of $H_{d-1}(S, \mathbb{Z})$, for a suitable measure on  random $\mathbb{Q}$-acyclic complexes $S$, would be Cohen-Lenstra heuristics --- the idea that the probability that a random finite abelian group is isomorphic to $G$ is proportional to the size of the automorphism group of $G$.
If something like this holds, then with probability bounded away from zero, $H_{d-1}(S, \mathbb{Z}) $ is cyclic.  If anything like this is the case, we should expect that there exist $2$-dimensional simplicial complexes on $n$ vertices with $p$-torsion, where $p$ is of order $\exp (cn^2)$.
Linial, Meshulam, and Rosenthal recently provided new examples of $\mathbb{Q}$-acyclic complexes, by defining complexes symmetrically on vertex set $\mathbb{Z} / p$ and then analyzing the Fourier transform of homology.
I did a little experimenting with their examples in SAGE and found a $2$-dimensional simplicial complex $S$ on $31$ vertices with
$$| H_1(S, \mathbb{Z}) | = 736712186612810774591.$$
This is a product of distinct primes, so it is necessarily a cyclic group.  (The largest prime factor is $408437$.)
A: I can build the lens space $L(p,q)$ with $16p+8$ vertices; this has $H_1$ (and $\pi_1$) equal to $\mathbb{Z}/p$.
We'll start by building some triangulations of $S^3$. Take two $2p$-gons, with vertices $(x_1, x_2, \ldots, x_{2p})$ and $(y_1, y_2, \ldots, y_{2p})$. Let $J$ be their join. This is a three dimensional triangulated manifold whose maximal faces are $(x_i, x_{i+1}, y_j, y_{j+1})$ for $1 \leq i,j \leq 2p$ (all indices are cyclic modulo $2p$.) Topologically, $J$ is the sphere $S^3$. Let $B$ be the first barycentric subdivision of $J$. $B$ has 
$$4p + \left( 4p + 4 p^2 \right) + 8 p^2 + 4 p^2 = 8p + 16 p^2$$
vertices.
Let $\mathbb{Z}/p$ act on $J$ by translating $2$ steps around the first $2p$-gon and $2q$ steps around the other. This induces an action on $B$, and the quotient $L$ is, by definition, $L(p,q)$.  There are $(8p+16p^2)/p$ vertices in $L$.
I leave it to the reader to check that $L$ is a simplicial complex. (You need to check that there is no edge joining a vertex to itself, and that any set of vertices is contained in at most one face. This isn't true if you use $p$-gons instead of $2p$-gons, so be careful!)
A: You might be able to do slightly better than with David's construction, but still with a number of vertices linear in $p$.  Namely, you present the group $\mathbb{Z}/p\mathbb{Z}$ by a single generator $a$ and a single relation $a^p$.  Now you triangulate the CW complex obtained by glueing a disk to a circle by a $p:1$ map along the boundary (this is the standard trick to produce a CW complex having as fundamental group any group given in terms of a presentation).  Let me be more explicit; in the construction I will give, I need $3p+4$ vertices, though it might be possible to reduce this number by a more clever subdivision (using triangles, instead of squares, for instance).  Let $a_0,a_1,a_2$ be the vertices of a triangle and let $b_0,\ldots,b_{3p-1}$ be the vertices of a $3p$-gon.  Add (triangulations of) the squares $a_i , a_{i+1} , b_{3k+i} , b_{3k+i+1}$ for $0 \leq k \leq p-1$ and $0 \leq i \leq 2$, where, obviously, indices are taken modulo the respective numbers.  This achieves the identification of the boundary $b_0,\ldots,b_{3p-1}$ of the two-cell with the fixed circle $a_0,a_1,a_2$.  Now we need to cone off the boundary of the two-cell: simply add a new vertex $v$ and all the triangles $v,b_i,b_{i+1}$ where $0 \leq i \leq 3p-1$.  Thus we have a simplicial complex with $3+3p+1$ vertices whose fundamental group is $\mathbb{Z}/\mathbb{Z}p$.
Finally, one more comment on the second part of your question.  Denote by $m(p,d)$ the minimum number of vertices $n$ needed to construct a simplicial complex with $n$ vertices and non-trivial $p$-torsion in degree $d$ homology.  There is an obvious inequality: $m(p,d) \leq m(p,d-1)+2$.  This follows at once from the fact that you can suspend a simplicial complex by adding two vertices; the effect of suspending is that you shift the (reduced) homology groups up one step.
A: UPDATE This version is substantially improved from the one posted at 8 AM.
I now think I can achieve $\mathbb{Z}/p$ using $O( \log p)$ vertices. I'm not trying to optimize constants at this time.
Let $B$ be a simplicial complex on the vertices $a$, $b$, $c$, $a'$, $b'$, $c'$ and $z_1$, $z_2$, ..., $z_{k-3}$, containing the edges $(a,b)$, $(b,c)$, $(c,a)$, $(a',b')$, $(b',c')$ and $(c',a')$ and such that $H^1(B) \cong \mathbb{Z}$ with generator $(a,b)+(b,c)+(c,a)$ and relation
$$2 {\large (} (a,b)+(b,c)+(c,a) {\large )} \equiv (a',b') + (b',c') + (c',a').$$
I think I can do this with $k=6$ by taking damiano's construction with $p=2$ and adding three simplices to make the hexagon $(h_1, h_2, \ldots, h_6)$ homologous to the triangle $(h_1, h_3, h_5)$.
Let $B^n$ be a simplicial complex with $3+nk$ vertices $a^i$, $b^i$, $c^i$, with $0 \leq i \leq n$, and $z^i_j$ with $0 \leq i \leq n-1$ and $1 \leq j \leq k-3$. Namely, we build $n$ copies of $B$, the $r$-th copy on the vertices $a^r$, $b^r$, $c^r$, $a^{r+1}$, $b^{r+1}$, $c^{r+1}$ and $z^r_1$, $z^r_2$, ..., $z^r_{k-3}$. Let $\gamma_i$ be the cycle $(a^i,b^i) + (b^i, c^i) + (c^i, a^i)$.
Then $H^1(B^n) = \mathbb{Z}$ with generator $\gamma_0$ and relations
$$\gamma_n \equiv 2 \gamma_{n-1} \equiv \cdots \equiv 2^n \gamma_0$$
Let $p = 2^{n_1} + 2^{n_2} + \cdots + 2^{n_s}$. 
Glue in an oriented surface $\Sigma$ with boundary $\gamma_{n_1} \sqcup \gamma_{n_2} \sqcup \cdots \sqcup \gamma_{n_s}$, genus $0$, and no internal vertices.
In the resulting space, $\sum \gamma_{n_i} \equiv 0$ so $p \gamma_0 \equiv 0$, and no smaller multiple of $\gamma_0$ is zero. We have use $3 + k \log_2 p$ vertices. This is the same order of magnitude as Gabber's bound.
A: Andrew Newman just posted a preprint to the arXiv, showing that for every prime $p$ and $d \ge 2$, you can get $p$-torsion in homology $H_{d-1}(K)$ with only $O(\log^{1/d} p)$ vertices. (The implied constant depends on $d$, but not on $p$.) This is best possible, up to a constant factor.
His construction starts with something similar to what Speyer describes above, which gets you a complex with $O( \log p)$ vertices. Then he applies the probabilistic method, taking a certain carefully chosen random quotient of the complex, gluing together vertices in a random way. This doesn't affect torsion in homology. The problem is that it might not result in a simplicial complex. But Newman uses the Lovász local lemma to show that with positive probability, it does. Hence there exists a vertex identification that works.
