Somewhat disagree with Hawksteer, but then again I am still on cheiftan level myself. I like to give them everything they want, maps and all, get tech, cash, etc. from them. Here is why;
When I begin a game I expand, and fast. Build warriors, then workers, then settlers. Generally I don't, nor do I have to, build anything else before I have at least three settlers from one town. Just mix 'em up with workers and warriors.
I begin by exploring, and big time. Looking for the goodie huts and more importantly the enemy (another civ). As soona as I find 'em I build up next to 'em and work my way back.
In the game I am currently on I have a mess load of towns, largest civ in all the world, but my poor city placement, mainly due to resources needed and terrain, I have left some holes. More dangerous is the large amount of unsettled land I have left, or rather barred from the rest of the civs, below my front lines. Those fools think that all because I haven't used it yet that I am never going to use it so they just walk right through my kingdom and start settling towns! We can't have that!
My problem is that I have two civs doing this to me at once, and I certainly cannot allow it, but at the same time I cannot fend them both off at once. So what do I do? I let 'em, or at least one of 'em.
Grease the palms of one of 'em while you build your army up. Give this one money, maps, etc... everything you can so that you can establish a ROP (very important). At the same time yell at the other one when ever they come on your land and try to bar them off by making a line of troops in front of them. If your at peace they should just turn around and go home, or hang out waiting for you too move (this better, because your going to get some workers).
When you get a large army up attack the idiot you've been yelling at, and ask the one you have a ROP with to help. I have never been turned down for help from someone I have a ROP with. Fortunatly, the one you asked for help with will not have that great of an army, since they have been expanding, mainly into your territory. They will attack once, but the idiot civ your at war with will slowly start to take over the idiot you made a pact with towns. Keep driving your forces in to the civ your at war with until you have expanded significantly enough. Then call for peace. Stop greasing the palms of the one who helped, and start greasing the palms of the fool you just tromped on. Raise another army, get a ROP with the other CIV, and attack the CIV that has already encroached on your territory. It should be pretty easy to take over or raze the towns within your "borders" that he has placed.
Sound complicated?
Basically, use diplomacy to your advantage. In your case, with one civ moving in on the land you want, I say let 'em, and let 'em think you want 'em to. Be very nice, give them maps to help them find good spots for their new towns, get stuff in return too. While they are busy expanding, you should be busy raising an army to take and protect these towns. Don't think of them as building towns for their empire, think of it as 'em building towns for yours. Hey, you might even get a leader out of it!
