I once wrote an A* algorithm to solve a 15-puzzle (the thing with 15 sliding tiles and 1 empty space, often depicting a picture, or just the numbers).
An easy heuristic that vastly improves the search: the sum of the manhattan distances of the pieces' current locations to their final positions.
So, as you said, rather than thinking about distance only in a Euclidean space, A* heuristics are much more general -- any metric that measures "done-ness".
For an AI course we had to write a solver for a puzzle using a heuristic. We had a reference solution step count to aim towards. After many hours of tweaking I still could not solve it. I had writ and rewritten quite complicated heuristics but to no avail, until at one point I stumbled on a nearly optimal solution. Upon reading my code again I noticed that a stray parenthes and a forgivinv lisp parser had caused most of my heuristic's code to be ignored. The simplest thing Just Worked :-)
This is a very interesting area of research. The state of the art in motion planning for robotics actually uses multiple heuristics at once with A*.
When I first read about A* a long time ago I remember, for example, reading about how static summaries of chess board positions may be useful heuristics. Developing pieces towards the center of the board is often better, for example. To me, seeing this was an "ah ha" moment for heuristics: use them if they are cheap and (sometimes) informative, relative to the search cost.