How to revolt and win quickly in Sid Meier's Colonization?

Solution 1:

Since I got back into Colonization, I discovered many game exploits and strategies I wouldn't have suspected. In fact, I dug so much that I more or less completely broke the game.

My best times so far are under 5 minutes for Discoverer and 15 minutes for Viceroy.
I hope you'll enjoy it as much as I did. I detail my strategy for Viceroy thereafter :

Summary

Here's a brief digest of my best strategy so far :

• Custom world with large continental land mass to help finding rumours and an ambush-exploitable mountain
• Sell starting muskets in europe to lower price
  & tools @indians to help buying some early horses, if you can
  Consider selling one extra set of tools, and/ore trade-goods/tobacco for money).
• Start with De Soto, and get 2 (max 4) scouts ASAP.
• Explore a bit but avoid visiting too much villages, especially if they give useless and time consuming map info, or if you fall upon Bastardwaks.
  Village best use seems to be checking the mood of the RNG (when villages grant you guides, rumours are very likely to give you fountains).
• Look for a streak of 2 (max 3) fountains, and some gold
  If you get Cortes, you can quickly farm 12+K gold. Else, just get 4 and abuse of tools trading
• With 4K and 20 colonists, you can tools-abuse (detailed below) to get the 13K needed for your army : 6K buying muskets & horses for 20 dudes, 4K for 2 extra merchantmen, 2.6K for 4 artilleries.
• Put 2 artilleries in your colony and the rest near your "REF trap" mountain, and you're good to start ambushing.

Starting the game

New world parameters

• Choose large land mass for more rumours
• Choose continents to reduce the chances your scouts get stuck
• If one of the other parameters provokes more mountain generation, it shall probably be chosen too... I didn't study that aspect, and doubt it exists.

Choosing your nation

• Dutch rule, as always.
  The starting merchantman is not only 1000 free gold, but also an extra move, which is extremely useful.
  The 4 holds also let you bring back both scouts AND sellable stuff when you get cool indians to trade with.
• English might be OK, since it will get your early scouts a bit faster and may help getting some guys before finding fountains, but I doubt it beats the Merchantman.
• Frenches don't seem of much use here. If you need to reduce tenses with a village, just give it one unit of rum / trade goods / tobacco sometimes. (and/or send missionaries in).
  Well, I didn't try them a lot... it might actually ease the war and enable you to keep more villages without problems.
• Spain is already quite weak usually, but is just completely pointless here
  The only indians you may be interrested in fighting are the one around your unique colony once you're fully grown-up, since they'll ambush you. Not worth picking a bonusless country.

Setting game options

• You can toggle the 6 first options.
  Autosave doesn't actually hurt, but is useless if speedrunning anyway.
  End of turn is necessary to avoid losing one turn before moving a unit in many situations.
  The 4 other options are just a loss of time, from a speedrunner POV.
• Don't forget to also remove the 3 last colony report options : you don't need extra pop-ups to tell you that rebel% increased.
  New cargo available is useless spam too. When speedrunning, unused stuff is because its unneeded. Noise about it being unused is just an annoyance.
• Removing food shortages warning (which may happen when you use several colonists to increase rebel%) and "report when colonist trained" (quite usual if you farm some "major beavers" for a few turns) seem counter-productive to me.

Landing

Choosing your colony spots

• Your 2 guys should fund 2 separate colonies to maximize production, and usually only produce bells.
  Harvesting some silver or a special resource for a few turns might be worth it, but be aware it will delay De Soto and the potentially following Cortes.
• Try to avoid sticking to any village if possible.
• Settle on special resources if you can, or even better, on an ambush exploitable mountain An exploitable mountain is one next to all the water tiles of your colony. That way, if you put guys on every close-to-water-square other than your mountain, you are sure the REF will drop on it, giving you a neat +150% ambush bonus.
• Since you'll probably have to look for said mountain, you'll usually wait for your scouts to find this sweet spot, and start off with temporary colonies.
• Choose Hernando de Soto as first FF. Restart if you don't get him. personally, for my speedruns, I ended-up just putting his weight to 999 in NAMES.TXT, and restarted if he didn't show up.

Early economy

• Grab your tools and muskets on your ship by visiting your two colonies.
  It might be worth waiting one or two turns to get the 50 necessary gold when horses cost 3, but I usually rather just rely on selling tools for that (to indians, or even Europe).
• Nomad indians are just not exploitable for trade.
  The only thing they may pay well for is your muskets, which are better sold in Europe (so that the price might collapse to 1/2)
• Other indians may yield trade profits (but are not necessary. Rumours remain the quickest way to get gold)
  Depending on the prices they offer, consider selling them tools, tobacco and trade goods. Don't buy tools more than once at Europe if you plan exploiting the abuse
  • When selling to indians, you may often rise the price several times.
    I usually stop after trying 5 times, but you may sometimes haggle more than 20.
    I got payoffs over four thousands ! (meh, shall try nine...) with cooperative Aztecs/Incas capitals.
    The important factor here seems to be the tensions/fear of the trading village.
  • Note that every village has his own offer/needs/fear lvl, and therefore its own prices.
  • Capitals seem to always pay a lot better.
    Consider building a temporary colony to reach one if it's only 1-square distant from the sea.
  • Consider giving one rum (or other accepted resource, but villages seem to always want rum) to ease relations.
    I bet this lets you raise prices higher, in addition to reducing the odds of getting attacked.
    It also lets you trade again something they "don't want anymore", in case you haggled too much.
    Checking Europe prices before you trade is a wise thing to do : know whether horses costs 100 or 150 for your scouts, and the prices or sugar/fur/ore in case indians want to sell you some.
• Once your ship is back to Europe, and depending on the prices you got from your tools, if already sold, you might recruit more than one scout.
  I usually prefer delivering the first immediately and go back then to take a second, while the 1st starts to dive into the continent.
  This also lets me buy one rum before selling tools, which I think is a good habit.
• You may also sacrifice one or two guys as missionaries (notably useful if you don't get enough money for horses with your first trip, and/or fell upon aggressive indians, since the mission reduces the tenses.

Building-up for Independence

Scouting

• 1st, NEVER visit rumours before you got de Soto (nor, with a non-scout unit). It's a risky waste.
• Your goal is to find 2 fountains and 4K gold
  Or 13K, if you don't want to abuse tools. This does NOT significantly take more time.
• Focus on finding lost city rumours
  • Scouting villages is rarely worth it.
    Scouting one to check what the rng is currently giving can help, but unless they give significant (at least 300) gold, I'd strongly recommend to skip the other ones, since this consumes time for little yield.
  • Also, be aware that Arawaks will kill your scouts about 10% of the time when you visit them.
    Any indian will do this if angered-to-death, but this extra Arawak-bonus is completely random, and unrelated with your relations or scout's expertise.
  • Note that villages upgrading your scouts to seasoned ones is generally an indicator that the RNG is in a good mood, which means rumours shall give you Fountain of youth (With de Soto).
    Experts scouts will get tales of nearby land instead, which slows you and isn't an indicator, since bad rolls grant this too
  • When you get a fountain, explore one or two more rumours ASAP, so that you may get a streak of 2/3 fountains.
    It doesn't always work, but if you're not too unlucky, you'll find some legendary cities of Cibola instead (experts are better at this), which is pretty cool too.
    If unlucky, you'll be back to rumours giving 50 gold, a.k.a. "you-got-screwed".
  • For those reasons, consider keeping one or two scouts camping near rumours, ready to wake-up when the fountain comes.
    Anyway, when rumours suck, try doing some other necessary things to give the RNG some time to change
    *e.g. look for or settle your mountain spot, trade with indians, bully europeans for money, or even convert your scouts to temporary colonies, to get a 2nd founding father *
  • Be aware that treasures get attacked very quickly by indians.
    Keeping distant from their settlement seems to be the key here (I got treasures waiting for long times at a 3 squares distance from villages without problems).
    Else, the ambush won't wait for long, and always succeeds.
    Good relations rarely prevent it.
• When encountering the other europeans, always threaten those sweaten pigs.
  They are dry for the (10?) first turns, but often pay well after that.
  Just don't farm them every turn, since it will give only 100 gold each time.
  You'd better wait a few (or more) turns before greeting their mayor again.
• Once you got all you need, DISMISS your scouts (unless they are still very close to your colony).
  A non-dismissed scout costs time due to indian pop-ups and the potential ambushes against him.
  Btw, it will also give his horses if defeated.

Buying an army

Considering the following assumptions :

• You have 20 or more colonists waiting at your docks
• The summed prices of horses&muskets is 6 or less
• You have a ship ready to load.

• If you plan to use tools abuse, price has to still be at 1/2 too.
  This should never be an issue unless you got a crappy map (or miserably failed :p).

  1. [ If you only have 4000 gold ]

     • Buy tools on everyone (you may sell muskets or horses if needed, but skipping those colonists is not a problem if you have some extra budget to afford the 600 loss of income).
       The abuse is that the price shall rise by one for every 200 tools bought, but won't yet. It will only rise if you buy/sell tools, or if a turn passes, and never fluctuate by more than one at once.)
     • Buy one tool with your ship. 8 times. Now, tools are at their max of 8/9 instead of 1/2.
     • Sell the tools from your ephemeral pioneers, for a 600 benefit per stack. You now shall have 12000 more gold ^^.
       Note that with only 16 dudes, you still end-up with 12800 gold. In other words, you don't even need to buy tools on your 20 guys, since you'll farm too much money. Just be sure to buy enough for the price to rise to 8/9.

  2. [ Once you have 12600 gold ]
     Here's what they are needed for:

     • 6K to equipp your 20 soldiers
     • 4K to buy 2 extra merchantmen (add 1 more K if not playing dutch, since your caravel lacks 2 holds).
       You may also skip one MM to save 2K, of course, but this means 3 trips instead of two. Talking speedrun... take 2 extra MM.
     • 2.6K for 4 artilleries.

• Btw, you may get a bigger army if you want, but this needs some more gold, AND will take some extra time, which counts when speedrunning.
  I'd strongly advise not filling more than an extra merchantman, since this would mean planning to have big fails from the army.

• In fact, a really minimalist army could use one LESS ship. For example, with 2 artilleries and 14 dragoons.
  Well, unless you hope for the RNG to get you insane luck, this isn't enough.
  The most "reasonable" minimalist army to me would currently be 20 units.

Delivering the Army

I looked for ways to reduce time lost bringing my army to my colony.
This takes a LOT of time. Really.
Here's the best I found so far :

• First, be sure you bought your ships/artillery one after the other.
  The units are played in order depending on their "ID number", so buying similar units together at once lets you play them in a row.
• Then, you'll probably want to remove the speciality of your soldiers, so they could get veterans.
  I generally stop or wait with my ships near my colony, and drop the specialists into it so I can fortify them immediately.
• To unload the others, I either move my ships in the colony, or if out of moves, manually activate them, and disembark through the city to a square next to my mountain where I fortify (ideally, all in one turn).
• The specialists left in the colony will all be speciality-cleared at once with simple select-enter-enter "combo".
  They'll meet their fellow unskilled mates one turn later.
• I think the optimal placement is to put 10 dragoons on the square from where you'll attack, and the 10+ other (as well as extra artillery) on another one, next to the attack square.
  You'll want all your troops to attack from the same square, to avoid having to check the situation for every unit you move.
  You don't want to fortify more than ten units on the used square, since units beyond the 10th won't be reachable.
• Station 2 artillery in the colony and the other outside to avoid having a too high defense value.
  They may also be useful for ambushing when your war ends.
  Note that artillery are NOT "in the open" when fortified (nor when attacking fortified units) .
• If you get a veteran soldier, station it in your colony so that he gets promoted when you declare independence.
  I think you need at least a 3-sized colony to promote a 2nd veteran, but don't have the exact formula for this, since I rarely do.
• Except for your mountain, be sure to have colonists or troops on all squares adjacent to water tiles, so that the REF can't land anywhere else.
  Troops should be moved safely after the (first ?) wave dropped, since the REF doesn't seem to re-analize the available landing areas unless one becomes blocked or the colony changes hands (which is likely to happen in the end of the war :p)
• If you still have indians around, beware : one could pacifically walk over your mountain... forcing the REF to capture everything.

Declaring Independence

Removing Indians

• I'd love to always keep all indians unharmed, but the game doesn't care as much as I do, and often gives no real choice.
• Thing is : the army you bring for the war of independence will frighten indians to death (often literally).
• The problem is they'll usually start attacking you right away, and will rarely stop unless their attackers (which actually repop) are all gone.
• Due to this, removing indians up to 2 or 3 squares away (at least) is usually a good idea.
  This might cost you significant army, which CAN be a problem, but could also give you one (or more) veteran(s) in return.
  A veteran is a cool thing to have, since it will be promoted to Continental if stationed in your colony.
  The treasures are usually useless at that stage.
  I guess they shall be dismissed unless they may enable you to buy some mercenaries during the war.

Fighting the REF

• Rule of thumb : always attack !
  If you enable the combat details (and more interestingly, the debug mode), you'll see your odds of winning fights are pretty high when attacking, and at best mediocre when defending.
  (See https://forums.civfanatics.com/threads/combats.97381/ for some combat mechanics details.)
• The main reason I put 2 artilleries in the colony is because we want the REF to drop waves of 4 regulars, one artillery, and one cavalry.
  From what I've seen, he does that as soon as you have 2 artilleries in your colony (even if one is damaged), but drops tougher troops if you go beyond 4 artilleries
  (I didn't look for exact numbers, or check with other kind of troops, but presume it refers to your units "combat values"'s sum).
  
  This 4-1-1 drop pace is optimal for you because it will quickly deplete the REF's supply of regulars, after what he'll just... surrender. This easily lets you skip a dozen cavalries, and one more artillery, which is why we need only 20 soldiers (else, you'd need about 35/40)
• Wake-up 10~12 dragoons, and attack from the square you chose.
  Try not to wake up too much, since you then have to skip their turn.
• RNG may troll you sometimes, and have all your soldiers fail.
  Then... just bring your 2 extra artilleries in the colony (you may start fortifying them via the colony screen), cross fingers, and for once... STOP attacking until next turn :|
• Anyway, some of your guys shall fail.
  At first, they still have their muskets, but then, they become useless garbage.
  Some ways of getting rid of them :
  • Fortify on the attacking square (you should have no remaining useful units fortified here anyway, so making them inaccessible isn't an issue).
    This is the fastest solution.
  • Disband. This needs one confirmation, and shows a bit of disrespect to those guys who risked their life fighting for you but... who actually cares ?
  • Fortify on nearby squares. E.G. to feed indians.
    You'll prefer them attacking your colonists rather than your army.
    Works for feeding the REF too once your colony is taken, this is just less reliable, but sometimes kills some regulars.
    Cost is just some little time (as well as your dignity... providing you had any)
• Note that if your colony falls, you usually have one turn to get it back before losing.
  In fact, if the REF is out of troops and you reconquer your colony, it seems you don't even have to eliminate his remaining troops for him to surrender(even if more than 5/6 bad guys remain !).
  I even had wins with 1 regular remaining in his reserves @Europe !

Miscellaneous

About the RNG

Ah, the pseudo-random number generation...
while it somehow does its job, the RNG in that game got serious flaws.

• The RNG is based on the clock. I lack precise details about this, but some facts remain observable :
  • First, you tend to always have similar results when visiting villages or rumours within a low time interval.
    This is why you can get streaks of fountains, and can generally be exploited to visit a lot of them when they are worth it, and just make a pause when they are not.
    I suppose this could also help when haggling or fighting (e.g. to get many veterans fast), for example.
  • The RNG also Sometimes gets stuck and only increases its value one by one (at least, for combat results).
    I don't know what provokes (or stops) this, but this can screw your whole army completely.
    This probably helps a bit too sometimes, but the tremendous attack+ambushes bonuses make winning attack streaks a normal thing anyway, so its hard to notice.

About Founding Fathers

• Hernando de Soto is the only necessary FF for a speedrun.
  It will ensure you fast fountains and treasures, which is about all you need to grab an army and kick the king's ass.
• Cortes is great too.
  Getting 100% of treasuries instead of 30% lets you farm more than 12K gold easily without having to use the lame tools-abuse exploit
  ...providing you take the time to get a 2nd FF, which costs 225 bells (the 1st only costs 56).
  Skipping some turns, this can be achieved quite quickly.
• Pocahontas is cool.
  Absolutely unnecessary, but rarely useless.
  I'd call it comfort.
• Brewster is disappointing.
  I thought it would make your army a lot better, since criminals and domestic take time to get veterans, but this seems negligible.
  Also, he has to show-up in your room before fountains filled your dock, which is quite rare.
• Jefferson is for Discoverer wimps
  and I'd fire him as soon as I'm aware of a way to get an early "Party" to improve the rebel% of my colony !
  We are talking Viceroy here !
• The other FF ? What other FF ? No. No, they are not worth anything.
  Not much for a "normal game" already, but definitely nothing for a speedrun.
  Or am I just a noobie unaware of the famous Paine-De Witt insane combo ? xD

Abandoned Strategies

Hard to remind things which didn't work...
one shall always list his unsatisfying attempts to prevent other for trying the same useless ideas.
Here are some I could remind :

• Rushing directly to the incas for great welcome gifts, trading silver, and/or looting big ammounts of gold
  • While unzooming and pointing the middle of the left edge of the map with a "go to" command often gets you to the Incas in a dozen turns, this isn't really efficient.
  • Dropping your colonists on the first turn (grabbing the tools&muskets back on your ship) virtually prevents any real lost when doing this, but issues remain.
    • The ~10 turns lost wandering make failed attempts fail much later, which is boring
    • I didn't try it with my newer improvements, but remember horses or muskets prices sometimes used to get higher due to those 10 turns "lost" for exploration.
    • Also, your initial colonists are just abandonned, as well as the free fur/ore their colony produce
    • Finally, the main initial idea was to loot the inca cities... well, fact is : you need an army for that, which makes it circular : this isn't a solution.
• Trading with a wagon train
  While this may sound surprising, buying a wagon train can in fact be VERY effective (costs ¤1040).
  • Supposing you trade with Aztecs/Incas, it lets you get 100 silver in return instead of 25
    I think 25 silver cost about ¤250, and 100 about ¤600, which raises the average benefit from ¤225 to ¤1300.
    In other word, your wagon is paid with one trip.
  • Also, the wagon may trade while the ship does something else (be it going back to Europe or giving rum/tobacco to ease trade)
  • I speak of trading silver, but clothes or coats can also yield nice profits sometimes.
  • While this technique may yield nice loads of gold, I still hate wagon trains. And facts proved I don't need that much money anyway. But the technique itself remains efficient.
• Sending scouts to the far edge of the world using privateers
  This is cool, and privateers are cool too, but with the different optimisations, this doesn't make sense anymore.
  • First, because a privateer costs ¤2000, which is half the money needed to buy an army using the tools exploit
  • Second, because it also means recruiting more scouts.
    I try to avoid having the horses cost rise above 4 now, since I want a cheap army.
  • The other potential uses for Privateers are just unexploitable in the short time of a speedrun, anyway.

• Protecting restock ponies inland
  Back when I didn't use the power of mountains, and used galleons filled with horses to "recharge" my troops instead, attack was so unreliable that I sometimes ended-up with my colony suddenly getting captured... and the 3 or 4 galleons in it were sunk.
  Needless to say I was wiped out in the following turn(s)
  
  So I got the idea of creating a colony where I put my galleons, then abandon it (galleons stay on the land square), and create a colony one square further inland.
  Repeating this, you may bring a ship to any inland square you want !
  
  ... this is just plain useless, yet. both because I used to lose when my last port was captured (dunno the exact reason why I didn't get a turn to reconquer it back... maybe because it's not my last colony ?), but also because using a mountain (and now, the magic "4-1-1" drop pace), you don't need so much troops anymore, and can skip the long process of sending your soldiers to your colony, unloading ponies, and changing them back to dragoons.
  But it was a funny idea anyway
  Good ol' memories from... well, a few monthes ago

• Building a few roads
  Building roads easiens troops mobility. Sure, mounted ones don't need it, but simple soldiers are slow, as well as demoted simple settlers and need two turns to first move to colony, THEN fortify, which is a loss of time and an increased chance of making mistakes.
  ...but good troop organization reveals this is a completely unneeded luxury.
  The ability to walk back from the mountain in case of mistake was supposedly useful too... but it isn't supposed to happen.
  If you happen to accidentally do this, just disband the unit with shitf+D (works even if it got no remaining moves)

• Building forts/fortresses
  This is not reliable at all. Note they can be bought with some extra money, so you could actually create some, but this doesn't seem worth it. When I used to buy a building, it was rather a printing press (hell, I always forget about that when all I need before declaring independence is getting those 50% SoL)

Final Note

While I tried to be as comprehensive as I could here, the best strategy is the one I didn't find yet.
There's always things to improve, and some of them are very situational.

For example, I sometime did buy some artillery before I get my army.
This doesn't increase the horses/muskets costs, makes room for some more dragoons when you'll buy the army, and more importantly, grants you some stuff to protect your colony if you had to build near an uncooperative village... or let you claim a sweet mountain spot which has been taken by a foreign European.

I enjoyed looking for all the exploits here, and think the strategies I found are well optimized already... but I'm also sure room for improvement remains, which I can't see from my angle of perception :)
Feel free to add improvement suggestions, if you happen to try speedrunning this wonderful game !

Solution 2:

Here's a speedrun I recently recorded (as discoverer) for a revolution in less than 7 minutes (26, or 27 game turns xD).
The only real remaining optimization I see here is to have the king surrender 3 turns earlier, which I got a few times. I suspect it might happens if your colony wasn't captured (which is pretty hard, or rather, luck-related, when you use a minimalist army).
Without a particular luck, you can't afford to sacrifice units to defend. Of course, retrying until a lucky run (ft. big early treasure) happens, but I prefer reliable and reproducible ways.

Since the thread Dylan pointed out is dead *off topic, I'll give in my two cents about playing on higher (i.e. Viceroy) difficulty
EDIT : now also speedrunned, in less than 15 minutes as Viceroy, as I'm editing the post. That game is easy after all ^^

-When I was young, I did craft many goods, start with Minuit/Hudson, sell furs, coats, rhum/cigars/clothes, kiss the ring, fear my fellow europeans, and so on.
-recently, I decided to try the game again, ahhh, nostalgia... I enjoyed it. a lot.
-But things changed. Here's a rough idea of how I go NOW :

• I don't usually alter land masses or climate, but for best results, continent-large land mass seems to be the obvious best choice to me. The main reason is you'll have much more lost city rumours (and indian settlements) to explore, which yields outrageous ammount of golds.
• If I want the best results, I take dutch. This isn't necessary, but I assume it should be if you aim for the fastest win. (except if you use the infinite money trick (see end of post), which requires playing anyone else, and is indeed faster... but feels a bit extreme to me. Well, thats another story.)
• When simply aiming to win, I noticed dropping my starting troops to rush an european, (in fact, usually two, and sometimes the 3) works pretty well. Players start at Y-positions 14/28/42/56. On generated maps, you, are either at 28 or 42 (middle), so depending on what you aim for, you know where to find one or two.
  Removing one of the guys already gives you roughly 50% of the territory for you ONLY, and a lot of free (and often skilled) colonists. You also usually get a free soldier (he funds a settlement), and his muskets, which is pretty useful, since you can let him stay on place to get the forthcoming replacement colonists, while your soldier can go take a 2nd extra set of muskets ^^.
  
  Though, speedrun-wise, you'd better focus on exploration.
  The europeans may be ignored, or exploited for some free gold : just threaten them every turn with a scout harrassing their mayor, and they'll often give 100-200 every turn. Yup, even as Viceroy !
  the point of disabling the europeans is also not to get flooded with retarded dragoons everywhere on your territory later, which doesn't matter here.
• if you get cool indians, trading tools&trade goods might still be of value. Some pay more than 1500 for their first tools. It's just very random. Well, on the other hand, your ship should be very busy... depends on which tribe(s) you find. Trade also lessens tensions, so you may consider giving one unit of #whatever sometimes (utterly lame, but very efficient :)). Personally, I consider trading isn't worth the hassle (except for the 100 starting tools, which easiens the recruitement of my first scouts)
• I don't bother crafting anything. My colonies already produce some free (and more often thrown for a fur-party than sold) fur anyway. My guys are more or less all producing bells to get the few useful founding fathers and the 50% bonuses useful to... get more bells xD
• Since I don't bother crafting anything, I need another way to get some cash. Buy ponies @europe on your first trip. If possible, get 2 scouts immediately (selling starting tools often pays for it). Else, get the second as fast as you can. Those guys have a ridiculousely high yield, for 100~150 gold only. Go scout every indian village you see. (use criminals if you have some, since they'll get promoted directly to expert scouts very soon). Some indian willages give more than 1K gold when you visit them. Exception : you may prefer skipping the Arawaks, since they tend to tie you up as archery targets (bug ???)
  When speedrunning, I now avoid buying more than 4 scouts (I used to buy 10-12, and carry 4 of them to the far edges of the world using privateers, but it takes time, raises mounts cost, and is in fact unnecessary)
• I don't enter lost cities rumours until I get De Soto. They might give something worthy, but will usually just suck. Once you get him, you'll get plenty of cities of Cibola (read 4K to 7K treasure) and fountains of youth (8 free and manually chosen colonists !!). Another thing which makes your experts scouts outrageously efficient.
• The first thing I used to spend money on after 2 scouts was some privateers. For a speedrun, it appears they are too expensive, but they remain incredibly powerful for a "vanilla" playstyle. I usually tried to stop after 4, since the game "seems to drastically increase their odds of sinking when you have too much", but they are clearly an abusable ship. Even just for transport or scouting, they are just too awesome. Getting free muskets or valuable goods is the icing on the cake :p
• Once the (new) world is mine, I peacefully wait for my scouts to get all the gold they can, then buy an army. Here's my current pick for a win : a mountain, ~20 dragoons (avoid servants and criminals as much as you can), 3 (or 4) galleons filled with ponies, and 6 artilleries. Farming indians can be an efficient way to get lots of gold, but except if you drop on aztecs immediately, exploration might be enough. Yet, it remains a good way to get veteran soldiers at low cost.
• Fortifications are a complete waste of time (and resources). You have to attack the REF troops with the (insane) ambush bonus. Never let yourself get attacked. (also, for that reason, I don't cut any forest aside water anymore. Ambushes are too precious.
  For a "fastest possible run", keep only one colony, near a mountain where the REF will drop all his troops. (the drops seem to work as follows : one Man-o-war chooses a (random ?) water square around your colony to teleport, then selects one (or more) of the free squares to drop army on (or drops over your -- now-captured -- troops). If all your water squares are adjacent to your mountain, just put a colonist on every other possible place, and the REF will happily jump into your trap.
  The only case where I let myself get attacked is when the RNG decides I'll fail all my attacks. That's the only reason why I added some (cheap and solid) artillery to my initial build

• I rarely accept more than 2% or 3% TOTAL as taxes (and prefer sticking to 0%.)
  Taxes are deduced when you get treasures, which makes exploration less abusable. Bad !
  Anyway, crafting good consumes precious time, and unless you protect them in wagons or ship every few turns, they'll get thrown if you don't accept a (usually too high) tax raise. This might be more questionnable when trying to win fast, but after completing several games in less than 1h30 on viceroy, I don't accept them more than usually.
  The only really annoying party is "horses". Since it's usually good to breed some everywhere... it tends to provoke it quite fast. For a normal game, I would recommend using Fugger as a "finisher" (i.e. to spend 30-40K buying and filling galleons just before declaring your independance).
  For a speedrun, just never keep unequipped muskets or horses in a colony before you declare independance

• The FF I hope to get, in that order :
  Luxury : De Soto, Cortes (mainly for Cibolas), Jefferson (skip him for a speedrun, he's not worth it before 5/6 fathers)
  Good : Brewster, Pocahontas
  Cool but unnecessary : Drake, Magellan, Minuit
  Too late : Bolivar, Washington, Stuyvesant, Smith, Fugger, Las Casas
  Useless : most other
  Negative : La Salle (stockade kills your flexibility.) , Paul Jones (a frigate is rarely useful, and I'm afraid increasing your navy reduces its efficency), Franklin (I dont want to prevent my king from giving me ¤500 and one or two goons for a war)

• Much more to say but... hey, I didn't intend to write a FAQ or guide ^^ Guess the question inspired me a bit too much.

[Useful exploits]

-- Flow of fountains --

The RNG in that game has some predictable patterns.
Avoid exploring rumours when one just gave something bad. And be sure to explore some more when you just found a fountain.
Keeping some scouts asleep near rumours will easily give you streaks of 3 or 4 fountains, which is enough to recruit an army when speedrunning. Also works with the (dangerous) burial mounds, not very interesting middle-range (~200-500 gold), or crappy "nothing" and "~50 gold" rewards, among others. very rarely with Cibolas :'(
Btw, when you get a bad reward (or unneeded fountains), consider doing many other actions triggering the RNG before you visit another.

-- Infinite money exploit --

Needs only 4 settlers and a ship at your european docks, cheap tools (they start at 1/2 and shouldn't have risen), and enough money to buy 400 tools.
The trick is that horses/tools/musket prices don't fluctuate when you equipp or unequipp colonists waiting at your docks.
Hence, you may equipp 4 colonists with tools bought at 4*200, then buy 1 tool twice with your ship (price rises twice), and sell the tools back at 4*300. Profit : 4*100. Every 200 tools bought, you may rise the price once more (up to a max of 8/9), which will quickly turn the benefits to big values (10*400 with only 10 colonists). Just sell back the single units of tools bought with your ship once your guys are desequipped to get tools price back to 1/2. (if you seem to get stuck at 2/3, consider training and unequipping a hardy pionneer).

Note that you should'nt have to buy much colonists when using this trick. Fountains should have already given you at least 8 (prefer 16 or 24).

Doesn't work as dutch, since prices don't collapse as fast as they rise, making you unable to get your tools prices down to 1/2 once sold. Doesn't seem to work as Discoverer, since the prices seem to rise faster than they collapse (same idea as playing Dutch). I didn't check the intermediates difficulties)
And doesn't work with ponies either, since their price drops faster than it rises.
Interestingly, this is exploitable in another way : just sell back your ponies everytime the price rises after you bought some, and it will stick at 1/2, at no cost (unless you accepted taxes, btw)

TL; DR :
Step 1 : Get some scouts & De Soto, explore a whole new world, buy an army.
Step 2 : ???
Step 3 : Profit !

Solution 3:

If you wanted the Fastest run, you could try looking around the civ fanatics speedrun thread, and seeing some of their scenarios. You may also want to check out some of the strategy guides for some ideas.

Generally, a fast way to win is to find a nice settlement with lots of fish and a lumbermill, and get a scout/guns with your first shipment. You'll then be on a mad dash to gather as many guns/horses as possible (mostly from the indians you scout out). After you have lots of guns, grab some statesmen, get some citizens from Europe and turn them into dragoons, then revolt. You should be able to take whatever Europe throws at you.