Most people tend to beeline for Early Empire. I beeline Craftsmanship.
You should be able to make up the difference with Policy management and saving the 1 or 2 forests for special chops (like settlers).
I wouldn't waste my time with scouts (rarely do), but I would use all of my first units to explore. Send one out to the edge of the unexplored map, then start moving him clockwise. Send the next one out following the same path, only further out, and the next and the next. This way you can explore but still have defenses near home, and hopefully spot any invaders. Your troops are exploring/scouting in an ever-expanding, ever-moving wheel. Once you have enough troops, you can let a couple wander off and keep the others close to home.
Once you've spotted a site with decent production, bomb chop a settler. Do it again as much as you can every time you see a good spot, even if it means crushing some cities together in tight formation. Conquest would be easier, most likely, but you seem averse to that.
Paste a jpeg. Its fun to study starts.
I don't know why I bothered posting. You obviously know all of this.
I've played quite a few Giant Earth Map starts with no hills around - even after hiking my settler for 13 turns. Its really not a problem. Little slower to get going is all. More civs will try to pick on you.
The really tough choice is what to build first? Warrior, monument, or builder?
One of the few factors that never changes regardless of game speed is distance. Distance equals time. So what you build first may depend on map size and number of opponents, and what civ you choose. But Craftsmanship cuts your unit production time in half, and monument gets you there much faster. Roll the dice on the zerg.
I dunno... nothing new here I guess. Maybe there is to someone.
edit1: well, here, maybe is an actually useful tip. On flatter starts, I will usually use my first builder to chop for a second, and the second for a third - in addition to chopping for settlers. So 1st builds does 1 chop for a second builder, then 2 improvements (often 1 clearing a spot for first district if necessary), and 2nd chops for a settler, 1 improvement, save, save, save, and chop for the third builder/2nd settler. Something like that. Also, since you are food-based, you obviously don't want to start popping settlers until you're size 3 at least, better at 4, best at size 5. Depends on the situation. Just do the worker-toggle dance until the pop. pops.
edit 2: it occurs to me that there may be some dissent in regards to my suggestion to go for Craftsmanship first. The argument I suspect to be put forth first would be that by the time you get Craftsmanship, you won't need it anymore, but will be ready for your first settler. This is 1) not true, and 2) the more cities you have, the more potential value Craftsmanship has. If you are in a position where more of your cities' combined production is going towards settlers than military units, well, at that point, who really cares? Your policies have become a bonus, and are no longer a crutch.