I also go path finding up and running. There's a good xna sample that I used as a basis and amended for my needs. For a goal cost estimation, which you need for some search heuristics, I thought I'd look up and use the arc distance. I'm getting pretty good at some calculations on spheres but every so often I'll seek out some formula and get a hell of a fright. Look at this demonic utterance.
|kill it with fire!|
|A* vs breadth first. Latter gets a shorter|
path but needs a large search space.