Convex hull on a Riemannian manifold

Q1. For sure simply connected complete and curvature $\le 0$ is sufficient. It is also true for any complete metric on $\mathbb R^2$ without conjugate points.

Q2. Almost no properties survive. I saw only one application of the convex hull in the Riemannian world. This is Kleiner's proof of the isoperimetric inequality in 3-dimensional Hadamard space. It used the following fact:

If $K=\mathop{\rm Conv}(X)$ then the Gauss curvature (i.e. the product of the principle curvatures) of $\partial K$ at any point $p\notin X$ is zero.

Concerning the convex hull of a three point set: generically, it has interior points in all dimensions; see my answer here.

See Jeff Cheeger and David Ebin, Comparison Theorems in Riemannian Geometry. Anton posted while I was typing, and Anton is an honorable man. The reason Q1 works as advertised is in the area of Toponogov's theorem, which tells how quickly two geodesics leaving a point must meet up again if sectional curvatures are positive. With $K \leq 0,$ the two geodesics are allowed to get farther and farther apart, and will do so if the manifold is simply connected. Remember, though, that the 2 dimensional torus has a flat metric $K=0$ and the higher genus oriented closed surfaces have metrics with $K=-1.$ In such cases, you still talk about geodesically convex neighborhoods of a point, when two points are joined by a geodesic arc that stays within the neighborhood, ignoring the possibility of geodesics that leave the neighborhood and return. This notion is also used in Lorentzian, pseudo-Riemannian manifolds.

EDIT: as this is for a class, it seems to me that the flat torus is a good example to go through, one can draw it as a square with identifications. Two distinct geodesics that meet once meet infinitely often, with various possibilities for the picture: in one case, take two closed orthogonal geodesics parallel to the edges of the square. As to points of the torus, they meet once, but as far as arc length parametrization of two curves, they meet infinitely often. The more typical picture is two geodesics at different irrational slopes, the set of intersection points should be dense in the torus.

EDIT TOOO: you have all those computer graphics, you could do convexity in the Poincare disk model of the hyperbolic plane. Then it is the quotients where convexity falls apart,

http://en.wikipedia.org/wiki/Fuchsian_model

http://en.wikipedia.org/wiki/Fundamental_polygon#Fundamental_polygon_of_a_compact_Riemann_surface

Convex hulls are extremely useful in hyperbolic/negatively curved geometry (in particular, I disagree with Anton's bold accessment in his answer that convex hulls have few applications in Riemannian world). Search on the phrases "convex core" and "hyperbolic manifold" to see how convex hulls help to work with Kleinian groups and (non-simply-connected) hyperbolic manifolds.

In the simply-connected case there is the following basic fact: if two convex sets $A$, $B$ in the hyperbolic $n$-space intersect, then the convex hull of $A\cup B$ is contained in the $\Delta$-neighborhood of $A\cup B$, where $\Delta$ is the thin triangle constant for the hyperbolic plane. (See e.g. Lemma 2.12 of this paper by Baker-Cooper). This illustrates fundamental difference of hyperbolic and Euclidean geometry.

One place where convex hulls appear prominently is the paper "The Dirichlet problem at infinity for manifolds of negative curvature" by Michael Anderson, JDG (1983), 701-721. My personal favorite application of this work (derived by Bowditch) is that in a simply-connected manifold of pinched negative curvature the convex hull of any quasi-convex set $Q$ is within bounded Hausdorff distance of $Q$. Surprisingly, this result requres that the curvature is pinched negative and not merely negative.