It is almost always a good idea to open up with scout scout. Yes, these scouts find ruins and snatch up workers like a charm. The thing is that the higher the difficulty setting the earlier workers appear for the stealing. So this strategy is more effective at higher difficulties. Stealing workers from the AI is very easy and they are often willing to make peace quite soon after. Once I have obtained a couple of workers and done some preliminary exploring I tend to go back home to protect the workers and improvements from barbs. 2 scouts and a warrior can keep those barbs at bay quite well. The Shoshone do pose a problem in that you can only make one pathfinder but they are stronger so they tend to fend off the barbs just as well. They just can't get the scouting and worker stealing done quite as easily.