I've discovered one counter-example. On a cylinder, I can come up with a triangle that have two angles that are congruent, however, the sides opposite those angles are congruent, too. Similarly, I can find an example on the cone. I am unable to find a counter example on a hyperbolic plane or a sphere. On a sphere, one has to distinguish what the "internal" angles are.
Regarding the cylinder and cone, this is when it falls into more than one "leaf," that is, when drawing it in 2-D.