The flip graph of triangulations

I believe your two questions are not directly related. As far as I know, Question 1 is open.

[Edit. I answered the 2nd question under the interpretation that "the triangulation graph of other surfaces" meant the graph of the surface triangulation, which, as Agol pointed out, is likely not what Mark meant. Rather he meant the flip graph, which is the focus of the 1st question. So the below does not answer the intended question. (The flip graph does not always make sense on a surface.)]

Let me address Question 2. For a long time, the fastest algorithm for finding the shortest path on a triangulated 2-manifold was the 1996 Chen and Han algorithm, which runs in $O(n^2)$ time for a surface of $n$ vertices. Here is an example from an implemention of mine with students of this algorithm, showing the shortest paths from one point to all the vertices of a convex polyhedron:

This and other algorithms are described in Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Section 24.2.

There was effort over many years toward improving the time complexity in the special case of surfaces of convex polyhedra, which was finally cracked by Schreiber and Sharir in their remarkable paper,

Schreiber, Yevgeny, and Micha Sharir. "An optimal-time algorithm for shortest paths on a convex polytope in three dimensions." Discrete Comput. Geom., Springer, 39 (2008), 500-579; Twentieth Anniversary Volume, 2009. 1-80. (Here is the earlier conference version.)

They improved the speed to $O(n \log n)$; the shortest paths are represented implicitly to avoid the $n^2$ complexity of explicit listing. This time complexity has only been achieved to-date for subclasses of nonconvex surfaces.

Just to add a little to Joseph's nice answer, for part 1 of your question: although the problem of computing the flip distance in polynomial time is wide open for triangulations of convex polygons, it can be solved in polynomial time for triangulations of certain highly nonconvex point sets (such as the intersection of the integer lattice with a convex set): see my paper "Happy Endings for Flip Graphs", SoCG 2007 and JoCG 2010.