The problem with some of these great ideas for terrorism is that they presume features in Civ that don't exist yet. And they're not simple features. And they're probably way more interesting in of themselves than terrorism itself.
Seperation between Civ and State: In the past Civs, you are the Civ. If you have a revolution, it doesn't mean anything. It's a nuisance. Then you get back to running everything. Only if your power is confined to the state can you have any meaningful detractors.
These detractors can resent you for many reasons, which can be explored throughout this post.
Nationalism versus Imperialism: The nature of Imperialism is that each of his subjects pledges allegiance to the Emperor, King, or Sultan. The ruler (and his dynasty) holds everyone together, no matter how different his subjects are. Nationalism is where people pledge allegiance to a flag, a land that belongs to everybody. Most importantly, a Nation is unified by a sense of common heretige, language, and values. An empire does not require this grassroots unity.
Nationalism often moves in spite of Imperialism. The Ottoman empire conquered a huge portion of land south of Russia/Poland, and East of Austria/Italy, and the Sultan ruled over many different subjects. Several "freedom fighters" began to get funding from intellectuals who believed that they were their own people, not "Turks". A massacre of 12,000 Turks occured, and thus began the war of Independance for Greece.
This would require features like rebellions, as well as a new cultural system to determine which citizens/cities have a common enough heritege to seperate and form their own Nation... A nation that hasn't been created yet, and may never have existed before.
Social Programs: And if you implement rebellions, you need to implement a way to prevent rebellions. It's not enough to be able to kill those who rebel. You'd need to be able to assimilate, pacify, or oppress them so they don't even think about rebelling. This means being able to make your empire into a police state so you always know what everyone is up to. Or this means making your empire into a welfare state, so the worst off have a decent quality of life and don't want to rebel.
And you'd need to be able to work with many shades in between these two concepts, since neither of these would exactly work well in their purest form, and nor are they diametrically opposed.
Crime and Deviance: A few poorly off people here and there might commit a crime. A frustrated segment of society who begins to identify with one another might cause a riot. Generations of frustration combined with deep intellectual thought might lead to full on rebellion and revolution. This scale would be absolutely necessary, or else rebellion would be random or inevitable -- and thus completely frustrating.
Internal Terrorists: Now, with all of these factors, you'd BARELY be able to explain a Timothy McVeigh. A single bombing due to a strange combination of social factors.
You'd probably be able to explain terrorists who feel oppressed by Israeli occupation. But Palestine is on that blurry line between rebellion and terrorism (I guess that blurry line will be resolved by hindsight). If they had real weapons, they might be a full-on Nationalist rebel movement. But they don't, and so suicide bombings and political attacks keep it more in the realm of crime than war.
--------------------------
Explaining international terrorists, though, you'd need a whole other set of factors.
Colonialism: A colony isn't a mini-town that you set up to extract gems before your borders expand. Colonizing happens when you send settlers into a populated area to run things, but have no interest in actually conquering the land. It's Imperialism's better-intentioned cousin. This is what Britain did to India. Or Belgium did to Zaire. Or Spain to Cuba. Or the Europeans did to, like, everywhere. Of course, why would you want to colonize and not conquer? In Civ, there's no reason for this yet.
Resource Consumption Even without getting into the advanced Economics, the reason you don't conquer an entire people and go to all the energy of building up more civilization around the world is because it's too high maintenance. Not to mention the reason you go there in the first place -- to acquire key resources that can improve the quality of life for your people. For your REAL people, not the ones that you're occupying, but for the ones back home. The key resource could be as industrial as oil or as luxurious as diamonds. You don't want to tap these and give them to the people you colonized -- you want to bring it back to the nucleus of your empire, and give the colonized crap on a stick.
But if consumption is so lame that only your military units need it, and they only require it to be built (no maintainance), who cares if you conquer more people? It's no sweat off you back.
Tangible Trade Routes Britain's occupation of the Suez Canal, or of India... they weren't necessarily for the resources themselves but the trade routes for the resources. But in Civ 3, trade routes are equally as efficient whether you have a single road across a border or a ship that has to go go all the way around a huge hulking landmass. This doesn't matter, so competing for key geographic positions doesn't mean anything.
Vassals: If colonizing improves on conquering in that you don't have to give much to the people that you're occupying, vassalhood is even more efficient. You don't do any occupying at all. You make a deal with the leaders of the nation. Or if you're feeling especially devious, you make a deal with rebels in the nation, help them take power, and they pay you back with those resources you so desire.
International Terrorism: If you've vassalized another nation and essentially made heaps of money from sucking away their oil, or their bananas, or their banana oil... The rebels might not pull a Timothy McVeigh against your puppet regime -- they might come right after YOU. Finally, we can explain SOME kind of international act of terrorism.
--------------------
Now look at all those features. That's just ONE possible path to explain international terrorism. This isn't even getting into how multinational corporations can provoke international terrorism -- and that's assuming Civ even has a private sector at all!
Another path that wasn't explored is how a unique situation like the creation of Israel could provoke international terrorism. You'd need to give people a reason to annex a chunk of land and give it to a bunch of refugees, instead of keeping it for themselves. If the only result can be international resentment against you for annexing the land, why would someone do it in the first place? There would need to be a motivation to give away land to a Civilization doesn't even exist in the way Civ represents a Civilization.
My point is when you look at that list of a dozen or so features -- you have a huge list of ambitious changes to make to Civ before you can even consider Terrorism. Terrorism is just a low priority because it's not feasible. That's even before you ask if any of the above changes like vassals are desireable for Civ. (I vote yes. But then I'd be happy to see them finish this list of features by Civilization 6.)
Random Terrorism: This is the last ditch alternative. Terrorism occurs randomly throughout the world, with buildings getting blown up. The terrorists either have no source or have a random source. This isn't particularly worthwhile if you ask me.
Inaccurate Terrorism that is grossly confused with State-Sponsored Espionage: People build units and use them to blow up each others' buildings, or kill civilians. The fact of the matter is that this already exists in Civ 3.
Inaccurate Terrorism that is grossly confused with War: You create a unit that fights other units. What makes it a terrorist is that the unit is called "Terrorist" and dresses and looks like a 13 year old's stereotype of what every Terrorist looks like. The fact of the matter is that this already exists in a 13 year old's Civ 3 mod.
