Here is a concrete example: let $C$ be the smooth projective model of the complex plane curve $y^2 = x^6-1$. Then $C$ is genus 2 and has a fixed point free automorphism given by $(x,y)\mapsto (\exp (2\pi i/3)x,-y)$.  

Geometrically: let $C$ be the double branched cover of the Riemann sphere, ramified over the 6th roots of unity. The $Z/6Z$ action generated by rotating the Riemann sphere by $2\pi/3$ and simultaneously swapping the sheets of the cover is fixed point free (but the points over 0 and $\infty$ are orbits of size two). 

If you are even more topologically minded, you can picture this as follows. Consider the graph with 2 vertices and three edges, each going from one vertex to the other. This graph has an order six automorphism generated by cyclically permuting the three edges and swapping the vertices. Now thicken this graph in three space to be a handle body whose boundary is a genus 2 surface. The previously mentioned automorphism acts on this surface in a fixed point free fashion.