OK, here's a starting point. I'll update it as we get more information here. The items I'm least sure about are marked with a question mark. Much information was inferred from the patch readme's. The points that seem to be the most important are in bold.
Civilization III (henceforth 'vanilla')
- Only one kind of Great Leader. Military Great Leaders (MGLs) can rush Great Wonders; Scientific Leaders were not introduced until Conquests. As a result, MGLs were usually used to rush Wonders rather than build Armies.
- Palace easily exploited for pre-building. The player could build it in more than one place at a time, whereas starting with vanilla 1.16f, it could not, so only one Wonder could be pre-built with the Palace at a time.
- Corruption/waste was severe. Forbidden Palace had higher priority. (?) Commercial trait didn't help fight corruption much. (when did Commercial become better?) The situation improved in vanilla 1.16f and vanilla 1.21f.
- Ring City Placement (RCP) exploit existed but wasn't yet discovered. Cities equidistant from capital suffered less corruption. (This did exist from the beginning, right?) This was effective until Conquests.
- Despot pop rushing extremely powerful. Sacrifice population by forced labor repeatedly to rush-build lots of stuff, because food is cheaper than shields in outlying cities with higher corruption and waste. This strategy was effective until vanilla 1.17f; see there for why. It was sort of the ICS of vanilla Civ 3: if you didn't use this "unnatural" strategy, you would be crushed by somebody who did. (Of course, multiplayer was only a pipe dream at the time...)
- Clear/plant forest exploit. Forest could be cleared for 10 shields, replanted, then cleared for another 10 shields. Fixed in vanilla 1.16f.
- Can trade cities with the AI. This led to some cheap AI exploits, for example, removing all the troops from a city, trading it to the AI, and recapturing the city with the removed units. Such exploits were fixed in vanilla 1.16f at the cost of no longer allowing the player to trade cities with the AI except in specific circumstances.
- Corruption alleviated. Some felt it wasn't enough; corruption-fighting ability improved again in vanilla 1.21f.
- Communal corruption in Communism for number of cities is now flat.
- Cost of palace now affected by number of cities. Now moving the capital is harder, but the palace can be exploited for pre-building in a large empire.
- Palace pre-build exploit fixed. A player can only build one palace at a time.
- Size 1 cities without culture will be auto-razed upon capture. Seems to be a way to make it harder for the human player to simply take newly-built enemy cities and use them for production. (Was there maybe another reason?)
- Culture-flipping happens more frequently. This helped "culture-bomb" strategies (rush-building cultural buildings in frontier cities), but made it harder to hold onto captured cities. (Did this have the indirect effect of making propaganda more effective?)
- Clear/plant forest exploit fixed. A given forest can only be cleared for the 10 shields only once; replanting and clearing has no effect. (Can a planted forest that wasn't there before still be cleared for 10 shields?)
- AI can trade on player's turn. This was either a bug or a deliberate attempt to fight "tech-whoring" (selling techs to everybody as soon as a new tech is obtained). This proved to be too cheap and the player cannot initiate trade on the AI's turns, so vanilla 1.17f fixed it.
- AI can no longer see invisible units.
- Cannot trade cities with the AI. The player may extort cities from the AI when signing a peace treaty immediately after war, and the player may give cities as gifts (and only gifts; the AI will not even pay 1 gold for a city), but that is the extent of city trading.
- Great Lighthouse weakened. It no longer allows safe travel into Ocean squares, making this Great Wonder a serious consideration mostly just for archipelago maps.
- Despot pop rushing strategy severely limited due to resulting unhappiness being cumulative (and also transferable if city is abandoned). In addition, the unhappiness penalty was increased to 40 turns until vanilla 1.21f.
- Infinite city growth with size 6 city and granary exploit fixed. (How did this work?)
- AI no longer trades on player's turn. This of course makes "tech-whoring" a viable strategy again.
- Military advisor bug fixed. The advisor previously would include Workers (and Settlers?) in its power calculations. (Did this go for the AI, too? The old "give 'em a ton of Workers and they'll declare war"?)
- Pop rushing unhappiness back to 20 turns again, but heavy repeated pop rushing still not very effective. Limited pop rushing can still be effective.
- Corruption/waste situation improved. Courthouses, Police Stations, and We Love The King Day are all more effective.
- AI more hostile toward non-military units in its territory.
- Seems to be mostly bugfixes and other changes and additions that don't alter strategy. However, the player can now disable the preservation random seed for a new game, thus allowing the old "if you don't like what's in the hut, reload the game" cheat for little wimps. You know who you are.
Play the World
- A whole bunch of new Civs added. Well, duh. However, new traits were not introduced until Conquests, so they were just like other civs but with different leaderheads and unique units.
- Civil Defense, Commercial Dock, and Stock Exchange improvements added. Wall Street also requires 5 Stock Exchanges instead of 5 Banks.
- The Internet Great Wonder added. Be like Al Gore and claim you have invented the Internet...
- Workers can build airfields, outposts, and radar towers.
- Probably a bunch of stuff I'm not in the mood to look up yet.
Play the World 1.01f
- Mostly unit and improvement tweaks. (Did any have any major impact?)
- Bombardment can destroy Airfields, Outposts, and Radar Towers.
There are no major strategy changes in any subsequent Play the World patch that I'm yet aware of; they are largely bugfix/tweak releases that don't change strategy.
- New Civs, traits, Wonders, and a bunch of other stuff added. I'll come back to this post later to add the details...in the meantime, RTFM.
- Free tech with Philosophy. This idea appears to be a nod to Civilization II. It also turns out to be powerful to the point that many players almost always beeline straight for Philosophy (after getting Pottery if needed).
- Statue of Zeus added. This Wonder has been shown to be extremely powerful by pumping out Ancient Cavalry every 5 turns as long as you have ivory.
- Great Wall changed. Previously, it would strengthen city walls; now, it adds city walls to all cities. This makes the Great Wall much more powerful and no longer so much a "booby prize".
- Secret Police HQ added. While it was supposed to work only under Communism, it acted as a second Forbidden Palace even in other governments (fixed in 1.13 BETA). However, you wouldn't want to actually build it: see next item.
- Forbidden Palace and Secret Police Headquarters actually increase corruption. Not true in every case, but true often enough to make them nearly worthless.
- Scientific Leader (SGL) added. Military Great Leaders can no longer rush Great Wonders, but can rush small wonders. A direct result of this is that Armies become more desirable to build.
- Curragh added. This early-game boat is often used by human players to explore the map more quickly and contact faraway Civs much earlier than they could before.
- Barbarians much more docile. Often they will fortify unless they see a stray Settler or Worker.
- Barbarians seem to pop out of goodie huts much more often. This makes early hut-popping not so good an idea except for Expansionist civs. Thus, the relative strength of the Expansionist attribute is increased.
- Double GPT bug. Atari's hastiness backfired and gold-per-turn agreements pay double gold. This often made AI players very powerful. Fixed in Conquests 1.10 BETA.
- Corruption system overhaul. One effect is the Forbidden Palace and Secret Police HQ can actually have negative effects, especially in Communism. Building them was now seldom a good idea. In other news, Atari's HQ has gone into civil disorder and Atari has fallen into Anarchy. Players charge that Atari is switching to Fascism. The corruption system is seemingly finalized in Conquests 1.13 and matches the original planned design.
- RCP unexploit. Now cities equidistant from the capital suffer more instead of less corruption, encouraging non-ring city placement. See previous comment about civil disorder and fascism.
- Agricultural trait added.
- Seafaring trait added. However, seafaring civs did not start next to the sea reliably until Conquests 1.10.
- Traits for vanilla and PTW civs reassigned. This changes the playstyle of some civs.
- Industrious trait weakened. Industrious workers work only 1.5 times faster than normal workers, down from 2 times faster. Enslaved workers no longer work faster. Forest clearing is not faster for Industrious workers. (Presumably this applies to swamp and jungle terrain as well?)
- Unit upgrade cost increase. A direct result is that Leonardo's Workshop is much more important now. (Umm...I forgot how much the increase was...)
- Zero-range bombard added for units such as Archers. This means they will get a free shot at attacking units, boosting the longevity of the archer and making it a reasonable possibility for garrisons in dangerous territory.
Conquests 1.10-1.12 BETA
- Double GPT bug fixed.
- Corruption system improved. Sort of. (Does this fix the anti-RCP problem?)
- Forbidden Palace and Secret Police HQ are weakened. (This is true in Conquests as well, but they didn't work properly at all; they're working in this version.) They no longer act as a second and third Palace, because the distance from the true capital is still factored in.
- Seafaring trait fixed. Seafaring civs start near the sea as they should.
Conquests 1.13, 1.15 BETA
- Corruption calculations tweaked again.
- Max corruption is now 90% instead of 95%.
- Cities with Palace, Forbidden Palace, or Secret Police HQ all suffer very little corruption.
- Forbidden Palace and Secret Police HQ add 50% to Optimal City Number (OCN). This provides a large boost to both the AI and the player, and the SPHQ may make Communism more desirable. Time will tell...(EDIT: We're not sure if in practice the boost is in fact 50%.)
- Secret Police HQ works only under Communism as intended.
Not sure what version yet
- "Zero-turn war" exploit fixed. Previously, the player could declare war on the AI (via renegotaiting peace treaty, then canceling it), then suing for peace before leaving Diplomacy. Now declaring war will boot the player from Diplomacy.
- Fixed huge cities exploit. Workers cannot be added to starving cities. Previously, a city that was starving would only lose one citizen per turn, so hordes of Workers could be added to a city to make it huge (despite it having a massive food deficit) to boost score in order to "milk" the game.
- Free techs from Scientific trait are truly random. Before, they were heavily weighted toward Monotheism (Middle Ages), Nationalism (Industrial), and Rocketry (Modern). Therefore, Scientific players cannot count on getting these specific advances for free. (This was in a PTW patch, but which one?)
To be added/fixed when I'm feeling less lazy:
- Info on Jaguar Warrior rush (when did it become less effective? I think this had to do with the retreat fix, but is it the whole story?)
- Details on retreat fix for fast units (their retreat is much less reliable)
- Any other major unit changes (help me out here, guys! )
- Clean up the list