We both agree that religion would be tough to implement. And we both agree that it would be complex. And we both agree that to just throw religion in for the sake of saying "hey, Civ 4, now with religion" would be a cop out.
But we differ in that I don't think it can be pulled off without copping out. If you avoid a cop out, you'll come up with a whole new layer of gameplay that is complex enough to be its own game. (Sim religion, as if you're playing as the eternal religious leader of a religion, and you have NO state, the state is your "enemy" or your convenient ally from time to time.) Or you'll end up copping out, as you say. In which case, we agree the designers should have done something else.
I raise several dilemmas:
Uniting Force and Dividing Force
How could you have religion tear Europe apart, first with the Eastern Orthodox, then with the Reformation and the Lutherans, Baptists, and Methodists ... and yet have religion unite Europe against Islam in the Crusades? And how can you model the tension between the sects of Islam, and yet have Islam unite against Christianity in the dark ages? And yet, how could that model never have produced a united front from the Western religions (Islam, Judaism, Islam) against an Eastern religion like Buddhism? And in said model, how can you have a religion that never splits into various sects, like Buddhism?
In other words, how can you model how religion both brought people together AND tore people apart? So far, every model suggested has only succeeded at doing one or another.
Spreading Force, and Colliding Force
You've talked about religion spreading, "be it encouraged or not, state policy or not". How can some states be contaminated by a religion, while other states resist completely?
How can the Vikings, who had their own pagan religion, become overrun by Christianity (which didn't even originate in Northern Europe, but in Rome)? How do the Vikings sack Northern Europe repeatedly, but the Vikings end up being the ones converted to Christianity, instead of converting Northern Europe to Viking polytheism? And yet, in the same model, why did neither Europe nor the Near East convert one another for all the war between the two?
Not to mention wars between France and Germany and Britain and Spain failing to spread each Christian sect, and yet Europe's conquering/colonization of Africa spreads Christianity. Why didn't religious boundaries change after either of the world wars, but religious boundaries changed a lot in the middle ages?
You'd need something that could model how religion spreads sometimes, and fails to spread other times. The models I hear about always seem to change with time, leading to constantly changing rules... not that that's a bad thing, but you have to acknowledge it if that's the case, as well as the complexity that comes with a game where the rules change all the time.
One Religion, Many States; One State, Many Religions
Modern US *and* Iraq can have serious amounts of religious pluralism, each leading to its own set of domestic issues. And yet, we can still talk about a time when multiple nations in Europe shared one religion, even though it experienced a level of tension and war against one another. How can you model religion in such a way that some states have multiple religions, and religions have multiple states?
If you're the leader of your state AND your religion, then of course you can order a crusade. But what if your religion is also the religion of Germany, and Germany orders a crusade? Or go the other way around, what if your state is Christian, Jewish, and Muslim -- how the heck does ordering a crusade work then? What if you order it? What if someone else orders it?
And how the heck does Judaeism stick around having seen Israel AND Juda conquered by the Assyrians and the Babylonians?
You'd need to model how religion transcends the state.
Control and No-Control
And if religion transcends the state -- which it absolutely has to, in order to cross borders, as well as having pluralistic nations like Modern America -- why would any state leader in their right mind accept someone else's religion, even in half their empire? What's the benefit?
You talk about how someone can engage in "religious anarchy" and flip their entire state's religion. If I were playing a game of Civ and religion kept on getting me into wars, I would make sure I flipped my religion or abandoned religion completely so that I could have more control over my empire. Show me the person with the most control, and I'll show you a winner -- no matter what the game.
And yet if players have no control, who is the decision making body who says when a crusade should happen, and who says which wars are crimes against God, and who tells 10% of the people in my empire that women should stay inside? And what would stop me from disobeying and saying "forget religion"?
Complex Answer
To find a balanced answer to the above questions, I can't help but think of a game where some people play as Civs, and other people play as religions. And sometimes the player in charge of Christianity is aligned with the players in charge of France and Germany, and sometimes the player in charge of Christianity takes a side, or promotes their own agenda. The religion-player makes decisions that control the will of its people, but those also belong to a state, and so those people have to choose between the state and the religion based on which is more powerful.
What you're talking about is two autonomous entities, religion and state, competing and cooperating as if they were state and state. And it's a complex game that's un-civ like. Not that it's a bad thing, but again, you'd have to acknowledge that.
I think more people on this forum will choose *not* to answer the above questions. They'll say the above questions are making the game too complex, and they should just be sidestepped.
Which brings us to the inevitable cop-out:
Cop out 1:
Religion will be controlled by players. Each player will get a religion as much as they get a state. Just as you spread your state with soldiers, you spread your religion with missionaries -- and for some reason you'd want to spread your religion without spreading your state.
The person in charge of the religion -- the player who invented it -- would get to order people of the same religion around. People would leave that religion to maintain decision making control over their people. "Sorry France and Germany, but I don't want to declare war on Persia and Egypt".
In other words, religions are alliances.
Cop out 2:
Religion is spread by the sword and only the sword. The player in charge of the religion gets to order people of the same religion around. Since people of the same religion are people who were conquered by them, they are ordering around their own people. So you say "Rome is now crusading against Persia".
In other words, religions are states.
Cop out 3:
Religions are something you choose as you go along. You pick one as you go along, starting out as pagan, embracing one of a few world religions by the middle ages, and dividing into more sects in the industrial ages. Nations of similar religions flock together. "We're on the Christian side! Let's go get those Buddhists!"
In other words, religions are teams.
Not a cop out? #4:
Here's one with *some* promise, in my mind.
Religions are not player controlled but are invented and spread randomly. There is no benefit to the player, they just spread, giving your nation identity and purpose. If you're Persia, becoming a part of Islam, Buddhism, or Christianity is a question of chance as much as it is geography.
In which case, religions are auto-teams.
And if you've ever played a multiplayer game where everyone on your team is a doof, you understand how crappy auto-teams are.
However.
Somehow I feel this one actually has more promise than the other ones. Because crusades and schisms and other such effects are not player controlled. The engine would force you to be historical -- with events taking place at historically sensible times. So you don't end up in a game where the whole thing feels like the middle ages, and every damn war is a crusade.
The Alternative
The designers have vowed to make Civ 4 no more complex than Civ 3. After they've simplified Civ 3, there's only a limited amount of room to add new concepts to Civ 4.
There are many other things that would be more interesting than glorified teams, alliances, or states under the guise of religions.
... and I think I can answer my own questions by re-vamping culture. For the reasons Sir Schwick suggested above.