I definitely second Eklaabian and Aussie Lurker's ideas. Allowing something as historically contingent as religion to fluctuate with game-play would be a major boon.
On a less ambitious scale, it would be interesting if combat units could carry individual religious affiliations (religion is, after all, in the eye of the beholder). Affiliation could be determined probabilistically as a function of the relative religious influences in the city in which the unit was spawned (at least at first, see below). If a city has, say, a strong Hindu presence (Hinduism has been there for awhile, lots of Hindu buildings and other Hindu units garrisoned there), but only a week Islamic presence, then the majority of units spawned there would be ‘born’ Hindu (with a rare minority born Muslim).
The consequences of this could be myriad.
-A unit in religiously sympathetic borders might heal at +10% (regardless of diplomatic status, and this could apply to one’s own borders as well).
-A unit garrisoned in a city of the same faith might gain +15% defense bonus.
-If a unit attacks a unit of another faith, it might receive a +10% combat bonus (fervor); but if it attacked a unit of the same faith, it might take a -10% hit (guilt, or some such).
-Units that shared the faith of a neutral nation with which you don’t have an open borders agreement could still travel through that nation’s territory.
-Even in war-time, if a unit shared the faith of the enemy, it might gain certain bonuses in enemy territory, such as use of enemy roads, +25% defense on tiles containing a cottage improvement, etc. This possibility could become somewhat strategic. Say one is running Buddhism but planning to fight a war against a Confucian nation. You might spread Confucianism to a key city and have that city build a few units for recon or pillaging purposes.
-Certain religious bonuses might be scaled by the number of sympathetic units (e.g., Organized Religion usually gives +25% build bonus, but this could instead be +5% for each unit of national faith garrisoned in that city).
-Certain events or wonders could modulate the above bonuses as well, for example, by granting units of national faith an extra +25% combat fervor, or giving all of one’s units immunity to fervor from all enemy religions, etc.
Finally, a unit’s affiliation might be subject to change. For example, a unit originally ‘born’ Christian, if garrisoned in a city with a strong Jewish presence, the odds of a ‘conversion event’ might steadily increase depending on how long the unit remains garrisoned in said city. An interesting spin-off here could be that, if a unit spends a considerable amount of time fighting in enemy lands (think crusades), this could increase the chances that the unit will convert to the enemy’s religion. In the short term, this might be good, as certain bonuses (see above) might be gained; but in the longer term, this might be less beneficial (e.g., garrison and healing bonuses would no longer apply once the unit returned ‘home’

.