Lets show your favorite Civ4 mods:

Fall from Heaven 2
https://forums.civfanatics.com/threads/mod-fall-from-heaven-ii.171398/
It turns Civ4 in a 4x dark fantasy game with all the depth a Civ4 has and then some. The mod was so good that the modder became (lead?)dev for Stardocks Fallen Enchantress (which while a cool game IMO lacks Ffh2 diversity).

Rise of Mankind - A New Dawn
https://forums.civfanatics.com/threads/rise-of-mankind-a-new-dawn.372884/
If basic Civ4 even with slowest speed and biggest world feels to quickly done and rushed: This adds A LOT. New techs, wonders & buildings for each era plus expanded length and new even longer taking speed settings will make your Archers still relevant and not replaced by tanks by the time they reach their destination. Also: Future techs.

The Authentic Colonization: https://forums.civfanatics.com/threads/mod-the-authentic-colonization-tac.440319/

I pretty much need this with me anymore when playing CivIV's version. It fixes bugs and issues, and generally improves on the game as a whole.

I play mainly the base BTS game but use the BUG/BULL mods and Blue Marble, or the wonderful BAT mod. These are graphical/ui enhancement mods that don't change the base game, which is extremely rewarding and challenging to play. I highly recommend these mods for standard gameplay (many of the mods mentioned below include it as well) BAT is bug/bull plus special graphical enhancements and is the mod I use the most for personal games. BUG/BULL is great for forum games over on civfanatics.com as it can be installed in such a way that shared games can be loaded without conflict.

With that said, I've played/tried quite a few mods over the years.

As mentioned, Fall From Heaven is fantastic (if a bit unbalanced-in terms of AI). I've played through the included scenarios twice, and several random games. But probably the best way to play is a succession type game with other players.

Civ IV obviously has some fantastic historical based mods. The following two stand out to me:

1) Rhyse and Fall of Civilization (RFC) - Just a fantastic mod which was actually included with the final Beyond the Sword expansion release. (Actually a little FFH game was included too but not the full mod). RFC is almost an historical simulator and the RFC map is actually engineered to reflect this..it is a smart map that makes certain changes during the game as well as city names and events. Furthermore, RFC has specific Unique Historical Victory Conditions for each Civ, some of which are almost like a puzzle to solve successfully. It is important to note that RFC has several very good modmods that add so much to it like "RFC: Dawn of Civilization", which adds many more Civs, to several era specific type modmods like Medieval.

2) Pie's Ancient Europe - PAE is a more era specific mod focusing on the Ancient World but is nonetheless a mod with a large scope and many many changes to the game. A very rewarding mod for fans of the Ancient World. PAE focuses mainly on Europe and Middle East of the time with a completely reworked tech tree that is more specific and detailed to the technology of the time. Reworked units and unique units and even Hero units can be achieved. One interesting feature is the ability to gain slaves which are like temporary worker units, but can also be sacrificed to rush production in cities or join a city to gain bonuses. Really detailed mod.

Many other mods exists, including quite of few "kitchen-sink" mods, as I like to call them. Basically mods that work like an expansion of the game in their own right. Mods like Realism Invictus, Caveman To Cosmos, ROME (AND) [ROME is acronym not the civ], Legends of the Fall, etc. Caveman to Cosmos is probably the largest and most extensive of all the mods and is still quite popular, but is extremely resource intensive. I've tried most of these mods at one time or another, but they are a bit much for me. Still, many folks like them and they have a lot to offer.

I would make a shout out to the "GEM mod", which is basically a map mod. GEM stand for "Giant Earth Map". However, it really is a full blown mod that includes some enhancements as well including parts of BUG/BULL via RevDCM. (Actually, a lot of mods include aspects of BUG/BULL) GEM is for folks who basically like the base game but want to play long slow games on a large Earth map. And really the gem of the GEM mod is the beautifully done and random Earth map it provides.

Lastly, note that all these mods can be found at "civfanatics.com", a huge and vibrant Civilization community. Great place to learn about the game, and modding in general.

Unfortunately, Fall from Heaven II isn't working on the GOG version. The 3.19 patch won't install, the mod itself just crashes at the load a mod screen.

If anyone can get it running, please tell me how.

Well, I just tried, and I had absolutely no problem (and I didn't had to install the 3.19 patch). I even tried to begin a game without issue.
When you were asked for the folder where to install the mod (and same for the mod's update), have you clicked on "browse" to locate it manually to specify exactly the good folder of mod's installation ? You should have "C:\GOG Games\Civilization IV Complete\Civ4\Beyond the Sword\Mods\" as path of installation (instead of "\Mods" which was by default)
Maybe it's here that you had an issue.

Please note that I'm totally new to Civ IV, it's the first time I was installing it of my life and so same for the mod, still, I hope this will help you :)

Whoops, I set it to Civ IV's mod folder instead of the BTS one. Thanks for the heads up.

Shouldn't the Steam and GOG versions of the game already be on v3.19?

No prob', always a pleasure to help, and glad it solved the issue :) (I encountered a similar issue with another game on GOG ;)) GOG's version is up to date (Beyond the Sword is at v3.19), concerning the Steam one, I don't know at all :P

Some highly popular mods:
1) BUG: Unaltered Gameplay mod, that greatly enhances the GUI and makes information easier to access, including some very useful information in the scorecard in the bottom right corner. I can't play the game without this now, it's simply great.
2) BULL. This is a DLL that changes a few things, and can be integrated with BUG. I like to use both of them.
3) BAT: Essentially changes some graphics to make the world look more realistic and 'sharp'. BUG is also included in this mod. Personally I don't use BAT, as it makes the gameplay a little slower, especially in the later eras, and more importantly, because I prefer the default look of maps, trees, terrain etc. But many love this mod, and it is definitely worth to check out.

You can download them all from here: https://forums.civfanatics.com/threads/download-bug-and-bat-here.274636/

Thanks - that is good to know

Anyone knows if the GOG version includes Civilization IV: Colonization Patch v1.01f?

Thanks

Caveman2Cosmos is the best mod for CIV IV in my opinion. It extends the gameplay from the very beginning to late game. However, you will need a 64 computer. When I installed it on my old 32 computer it constantly crashed.

Dune Wars http://www.moddb.com/mods/dune-wars

A Mod set in the Dune universe by Frank Herbert. Every Dune fan out there should try out his mod. For those who haven't read the books this mod won't probably give much.

All the important stuff from the books are present: the planet Arrakis, worms and spice. You can play as one of the major factions in the series: The Artreides family, the Harkonnens, the Fremen, and others. The mod has a lot of custom art and 3d models to set up the right mood. Check it out!

It should work now!