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.
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".