My first explorer goes straight out in the most promising direction looking for contacts - if he reaches the coast he will follow that round - still looking for contacts. My second will usually be looking for a good second city site first, and then will cover the other directions not covered by the first. The third will usually scout around for the next couple of cities before coming back for MP duty. If I am coastal I will try to get a boat in the water as soon as possible, simply because they are faster.
All units move N, E, W or S in preference to NE, NW,SE,SW wherever possible because they will travel further (this is particularly noticable with ships)