Just to add a little idea of my own; I personally think Regicide (as sort-of mentioned earlier in this topic) would be an interesting victory condition (or at least something that could add to victory) that wouldn't necessarily require there to be a state of war.
The leader of each nation would be represented on the map as a Hero Unit and each could possibly get unique bonuses according to the leader they are (be it a bonus to combat with certain types of units, a +% production bonus to troop training in a city, whatever) as well as some basic bonuses common to all that are present (eg giving a bonus to happiness when present in the city. Not necessarily happiness though, but perhaps 'stability' in some cases. Perhaps a bonus to culture whilst present?).
Akin to the Shogun leaders in the Civ 3 Conquests scenario, the leader would be upgradable throughout the game - depending on what techs are available and what kind of leader they are in the first place (so some turn in to fine warriors, some into Archmages; for instance the upgrades for Sheam leaders might come on the Magic line of tech whilst the upgrades for Hippus' leaders would likely be on the Riding tech line).
The leader could be killed in a variety of ways.
The first is, obviously, in battle. This could cause a Civ to be knocked out of the game and for their cities to go to whoever is culturally dominant there (or whoever has the nearest and largest army nearby). If there is no specific cultural influence from another nation, a city could become Barbarian (or join the ex-Civ's closest allies).
Alternatively, a leader could be assasinated. If an assassin finds the location of the leader, they could then attack them FIRST. There would be a chance, however, that they fail automatically and end up fighting with the strongest unit in the stack (or weakest, depending on whether or not they have Marksmanship which might increase the chance of a confrontation with the leader?). If the Royal Guard are present, success has an incredibly slim chance (unless they have Marksmanship). When all is said and done though, a leader might have some kind of bonuses (through experience or in the nature of the leader themselves) that help them against assassins (some leaders may be more paranoid and invest naturally in traps or be harder to locate whilst others who stay in one place or hang around in the open, flaunting their power may be easier to assasinate). Additionally, buildings (like Castles, Dungeons, Palaces) might lower the assassins chance of success.
If a leader is assassinated, then Anarchy sets in and civil rest occurs throughout the civilization. Cities may flip to other nations or declare themselves independant (Barbarian/Minor Nation?) if they were already unhappy.
A leaderless-civ might survive (apparent heir? hasty elections? coup?) though, dependant on a number of things. If their economy is doing very well (one of richest three nations?), then its decided that the merchants or nobles take over the countries ruling (if available, Aristocracy and/or Consumption civics are switched to with no chance to change for a while? A sort of temporary enforcement). If the nation has a large army (size of army is within top three nations?), then its put under Martial Law (temporary Despotism/Military State?). If a Holy City is present in the nation and the majority of cities have this religion, then the Priesthood take charge (temporary Religion/Theocracy?). Perhaps some others too. If one of these isn't met, the nation is 'dead' and is broken down into independant states (barbarians) or joins other nations.
Because of the loss of leader, a surviving nation would lose its Civ traits (good and bad? Just good?) perhaps? It may gain new ones, dependant on the 'new leadership' though (Financial or Organised for Merchants? Aggressive or Raiders for Military? Spiritual or Philosophical for Clergy?) but only one new trait would be obtained. Seafairing may be untouched for issues of balance?
If a nation DOES survive the assassination or the attempt fails, there is a chance that they can uncover who sent the assassin. If they do, it creates a BIG penalty to diplomacy with that nation (and makes later attempts harder?).
The last ideas I had at the moment for a sort of regicide was through magic or an Armogeddon spell of sorts to control or curse/kill a leader.
Casting the first spell would cause a random leader to gradually come under your control (at the end of a set number of turns, the leader becomes your unit to do with as you please which could then perhaps convert other cities? The nation left behind would become, after a turn or two of 'thinking things are normal?', like that of one who had lost its leader to assassination. This new leader could, of course, be disbanded instantly which would have the same effect. Alternatively, he could also be added in your own civ as a 'super specialist' or, in some civs, put in a cage to bump up the GPP nicely).
Casting the second sort of spell - the curse - would cause a leader at random (or perhaps ALL leaders?) to gradually suffer from a wasting sickness, permanently lowering his strength, little by little, every turn. The presence of various healing buildings in a city - and a High Priest - would slow this process but couldn't reverse it. The only thing that could completely halt the process is a Wonder of sorts, buildable after the curse is set. This wonder would either instantly stop the curse or give a bundle of resources that allow the construction of something incredibly cheap (1 hammer building) that stops it. The advantage of the 'bundle of resources' (say, the wonder gives 6 'cure' recources... and perhaps life mana? or it may require it?) is that these cures could be given to other nations suffering from the curse to stop their leaders dying (which might shift power in an interesting manner). The original 'curse' spell may also provide one or two cures as well so that the one who originally causes it is 'immune' or is in a position of power to trade it off to others so they don't suffer its effects.
A nation that loses its leader to the curse may also suffer unhealthiness in general but may act akin to a nation who's leader is assassinated (and so might remain in the game).
Of course, most of it probably isn't remotely possible and I really shouldn't try imposing anything upon you at all after all the good work you've done so far, but I thought I might try brainstorming a thing or two and see if I did anything useful ^_^;