More, give me more text to read, pliiiz :)

Well, my primary concern is the location of a province/planet in relation to other provinvces.

Check this very simple wargame http://www.kongregate.com/games/uunxx/hex-empire?acomplete=hex+empire Notice how the gameplay changes when you select another (randomly generated) map. Also, how replayable it is... The strength of the design of that game comes from the relation & distance of one hex to another. The underlying map block is really simple (empty land, port, city, water, and a special case of a city - capital).

I think (and also some people above mentioned it as well) that influence system might be the answer. Some sort of radiating of influence over neighbour tiles. Also not just binary 0/1 contol of terrain, but a degree of control (like: minimal, weak, average, strong, full). It could also use "political power makers" or "player agents" (as mentioned above by others) and maybe "deck of cards with disasters".

Something like this kind of mechanic comes to my mind right now:

- you run a space empire, everything on the map is either yours or neutral (no AI controled empires, purely assymnetric)

- you spead your "good" diplomatic influence, every planet that was exposed to it long enough joins your empire

- there are rebel events that spread "bad" influence, these reduce stabilty of planets they affect

- you can put some "political markers" or other "agents" on certain planets to stop/slow/revert the spread of bad influence (preferably in choke points)

- planets are divided into areas (systems/sectors), a sector share some properties also there is a domino effect within the sector, if there is a lot of bad influence even unaffected planets start behaving rebelious and where there is a lot of good influecne the bad influense spread is slowed within the sector

- you can build some infrastructure (bases?) that would spread your good influence

- there can be various paralell influences, not just good/bad, it could be rebels influence, support for the usurper to your throne, stability & loyalty, certain ideals/virtues (like if people believe in economy or are warlike or spiritual or cultural, these could affect hoew the planets are developing) etc.

- various agents can affect various influences at once, for example if you send an army (with pacification order) on one planet it will start reverting rebel influence but it will also spread unhappiness.

That one: "Player A does not play by the same rules as Player B (which may be a computer), yet they are at odds with one another."

Or to clarify even more, the player and the computer (since player B would not make sense in that particular case) play by different rules. Actually, "AI" could be just random events and primitive mechanics (like spreading disease/influence over land).