2)compute the normal of each object to make them walk on the sphere.
You wont compute the normals of the moving objects, you will compute the normals of the planet-sphere. the planet-sphere will have a normal for each polygon that makes it up. The sphere is made of many polygons, right? On each polygon that makes the sphere will have a normal to compute. the normal of each polygon of the sphere will be perpendicular to that polygon which makes it the perfect vector (the normal vector) by which you need to align your moving objects.