Techology stealing has a certain espoinage cost, and I'm wondering how its calculated.

For example, I was about to spy on Churchill, who had a cost of 1900 (even though I was 111% on cost with him).

For saladin, who I was at 89% cost, it was 3900.

And then when I got my spies to churchill's land, the cost jumped up to about 4000.

It varies from city to city. I think cities closer to your capital will have a lower cost, as will cities with lower population and the presence of your civ's state religion. On the espionage screen there is a listing of known cities for each leader, showing costs of different missions in that city. Peruse the list and find the lowest cost compared to all the others. Cost to steal a tech will still vary based on how expensive the tech is beaker-wise, so the cost listed on that screen won't be 100% accurate. It will give you a ballpark figure though (usually for the lowest-cost tech you can steal from them) and you can get an idea between that and the map of which city will be your best target.