Stealing techs is harder because your tech level is so much more advanced than the AIs' tech level. As others have said, the espionage system is geared to help civs who are behind in tech, not those who are ahead. If your tech level were closer to the level of the AIs, stealing techs would be easier. (Or so the theory goes.) Thus the suggestion to increase the difficulty level: on harder levels, you won't be as far ahead in techs, and therefore tech-stealing would be easier.Now, before anyone conjectures that those large numbers are because the Difficulty is set too low, stop and think: If the Difficulty is _easier_, why would stealing tech be _harder_?
Now, I don't know if this theory has been proven or not. It stands to reason, though. Why would super-advanced civs want to steal techs from their technological inferiors? It makes sense for the game to prompt advanced civs to do other things with their spies, such as counter-intelligence or CS shenanigans. Think of the ridiculous steal time as the game saying "hey, it'd be far more advantageous to do something else with your spy, you're clearly already pwning at the tech race."
(Though, I still think something is off here. As I've said, I have played many Marathon games on Prince and King where I enjoyed tech superiority similar to--and even greater than--what you've described, and I've never seen anything approaching 100+ turns for steal times.)
I'm not sure why you're caught up on comparing your cities to the AI cities. Your capital vs. theirs, your #2 city vs. their #2, etc. Again, I don't think the Potential of your cities factors at all into your stealing chances/rates. It factors into the AIs' chances/rates. (If I'm totally wrong about that, please someone correct me!)I sent a second agent to another city that had a Potential of 4-1/2 stars, and a tooltip = 3,300. My #2 city has only 3-1/2 stars, and the tooltip = 2,619. Now, after that second agent did his Surveillance and began Gathering Intelligence, the starting counter was _130_ turns. Which is odd, because while the other three cities have Constabularies (-25% chance), the target's #2 doesn't.