On Immortal, send your starting warrior to the capital and explore around it while waiting for their first settler. Steal that, then any subsequent settlers/workers they produce.
On Deity, they will start with a 2nd settler. Once they've planted it, and the 2 workers they start with have improved the 6 tiles around the capital, they will walk towards the 2nd city. You catch them in between (though not if the tile can be shot by both cities and the unit is not a spearman or tougher) and then back out the next turn. Watch for warriors that can get in your way or kill you. If you back out of the range of the city and a warrior does not follow, heal there and hover (if the unit is not needed to escort the worker, which it shouldn't be). You may be able to get more by repeating the same thing. The AI is not clever about it.
My record is 6 from AIs and 2 from CS before T32. Good luck!