On cultural victory (which might be the hardest one to aceive on an avaerage map save for some civs like sidar which have it by far the easiest and can aim for that one easily even without much knowledge of were you get lots of culture. Their shades alone will do solidly enough...):
You really have to plan that one well ahead (best whould be from start of the game. But by turn 100 at the latest you should know you aim for it. Otherwise you will experience what you did in the game you described).
Most important for that one are that you join the overcouncil early (only good or neutral civs can do that after they have researched honor by adopting the overcouncil civic) then make sure that the liberty-resolution is passed (be warned though to prepare for serious! happiness issues should you get into a lot of wars. And any offensive wars should be either conducted very fast of be a big no-no.)
That forces everyone in the council to adopt liberty (a civic usually only available much later into the game at mercantilism.)
That civic gives you a whopping +100% on your cultural output across your empire + the ability to run unlimited bards and as icing gives a free specialist for each city.
(thats aceivable around turn 150 even at emperor / immortal if you really aim for it and get quite lucky with your game... You needn't even get to honor first. Just get someone else to found the empyrean and trade honor + join the overcouncil. But be the second one if you can, so you can be sure you are beeing elected head councilor for at least one season so you can propose liberty. After that it doesn't matter anymore since AI usually doesn't topple passed resolutions + you always have your vote...).
The drawback is that you miss out on some very good other civics with regards to hapiness mainly.
Then try to fetch the perfect lyre wonder/item from Drama tech which gives another whopping +100% Culture + a few base culture (4 i belive) in the city it is build.
That thing can also be picked up and dropped in other cities. (which is greath when bringing up new cities to fat-cross influence as well.) Just pump the culture of one city so you reach an ammount were going legendary is easy, then focus on the next city. Until you have 3.
One drawback though: That wonder is quite an expensive one. Not much in the game is more expensive than the lyre so plan for some time (good thing about that: AI tends to avoid it for some time usually so you should be able to fetch it if you really want.).
Also each temple adds another 20% so getting many religions and spreding them to you 3 legendary wannabes really helps (5 temples each makes for another 100%. No need to found them. Just trade for the techs and spread liberaly). You can insta-build the temples of your state religion by building priests (priesthood needed for that.). But your 3 Legendary cities should be able to build those temples on their own usually. Only that priest-spread is automatic.
Then there are some other wonders like the grand menagerie and the theatre of dreams which allso add 20% each i belive (the theatre also will improve the cultural output of all bards a bit each. So worthwhile to get if you know early you are going for that victory.)
Then there is the caste-system civic (available with taxation) which adds a +2 to each specialist and the hall of kings wonder (available at feudalism) which adds +2 to each specialist. (so together with the theatre of dreams it makes for a whopping 9 Culture from each and every bard you have. Base. And a free one from liberty as well). If you are utterly diehard you could also adopt foreign trade (for another +20% available at trade) but usually Guardian of Nature (if you run Fellowship of Leaves) or agriculture civics are more interesting usually (because these allow for running a lot of additional specialists which nets better and is better for the rest of your empire as well)
Then there is a spell which helps (hope, spirit 2 for +4 culture base +1 happiness also available to honor guards a mounted gardsman UU available at feudalism for running the aristocracy civic. Even if you don't have spirit-mana. This spell also grants courage to all units built or passing by in the city its active.

)
And with the bonus of about 300% (if you can really grab / conqer all those.) and just 5 Bard Specialists (much more are possible usually. 10 in 3 supercities is doable if you only go for cultural, which also produce a neat ammount of greath bards for greath works.

) in each you whould have base culture of about 150 cultural output a turn alone from this (and the +3 from OO temple and some other smaller cultural sources from base buildings which i did conveniently include) (100 in the cities without the lyre).
Add wonders, buildings, economy--->culture and greath works into the mix, and its not all that hard anymore to reach 50000 per city early enough.
And if you really want to get the last bit of culture milked out of your empire you can also produce desciples (tier 1 religious units which are buildable at the base religious tech after building their respective temples for 60 hammers.) which sacrifice for "mini greath-works worth 20 culture each"
(Beware though that ashen veil-desciples can't do it. CoE has no divine Units in the first place so nothing from that religion as well...). Quite tendious micro but you can get quite some if your empire is big.
On the altar:
That in fact is one of the easiest builder victories available. Spaceship in vanilla should be by far harder. An Altar victory in the timeframe of Turn 300- Turn 400 should be no big problem if! you are! determined (and its also the easiest one to gain no matter the situation if you decide later on which victory you pursue.). Also the farther you get the easier it becomes and the more benefits you reap. Only the very start is rather hard.
First, and that is mandatory, you can't be evil if you want to build the altar (its something akin to human ascension to godhood. The evil guys don't have such "high and pure" goals.).
Also the higher levels of the Altar make the priest-specialists you need to run anyways to get enough greath Prophets really worthwhile (+ add lots of other neat benefits to the rest of your empire which are worth a wonder each in their own right.)
From Level 3 on each priest produces 2 Hammers (so akin to an engineer-specialist), from Level 5 (which is even rather early and on a usefuly place with fanaticism) on each priest produces a whopping 3 hammers. Also the higher levels of the altar offer priest-slots on their own allowing for an even faster production of priests. The farther you get, the easier the going will become.
Because of that its good to stockpile some prophets first (the first 2 until you get your 3rd might be a good idea. Especially if you go with Empyrean Religion since then it might be worthwhile to build the altar in the holy city of that religion. Not reccomended in competative multiplayer though.).
It really works for any nonevil civ (and you can switch alignments if you play an evil civ by adopting a good or neutral-good religion early to midgame rather easily. For a late switch its even easier usually.) but best it works for Civs with a religious focus (so any spiritual leader will do fine, as will philosophical ones.) most notably Malakim and Elhoim (Elhoim should work best of them all, especially with Einon Logos as your leader) as well as the Elves and Dwarves. Sidar oddly also work out nicely even though they explicitly focus on nonpriest-specialists with their specials.
The key here is that instead of getting many religions by yourselves you should focus on one (you should try to research / found that one by yourselves or grab the holy city if you can) and go down the line of needed techs fast at least until priesthood. (Best for that seem either Runes of Kilmorph. Octopus Overlords or Order with Fol and Empyrean also possible but a bit less gainful.)
Getting other religious techs later by trade or short cheap research might still be worthwhile but you shouldn't invest to hard in them.
You might want to get your first 3 prophets as early as possible. The earlier, the easier / faster the victory will be. So your first aim should be mysticism (after some base economic techs perhaps, like education. But going for mysticism first might also pay off, hard decision. I still usually go with education first.) so you can run priests as early as you can. (One sage for an academy might still be worthwhile. So don't just build a pagan temple, but an elder council as well but the pagan temple should be first. And run a sage + a priest until you get your first greath person which will be much faster that well. If thats a priest you get really lucky and can continue to run both. If you got a sage, get that academy and singlemindedly focus on priests from that point on. Which will delay the whole thing a bit.) Running pacifism (from the time you get your first temple / council up) until you have your second greath person might also be worthwhile (after which a switch to religion usually is better. Otherwise you will be crushed by maintenance or hapiness issues.)
If you start the game as either evil or good and are extremely lucky (or if you explore a dungeon and get extremely lucky) you might get a greath prophet or even 2 early in the game (you will need to have about 100 Gold handy so huts with gold or running Gold a few turns might really be worthwhile if you are determined to go for the Altar early.).
Should you get one don't waste him on your religion at that point (if you get 2 you are rather safe anyways and might go down the route of needed techs even faster ignoring some other techs you might otherwise want.). It might be tempting and the research-time might be long but you'll regret it later.
Then go for your religion if you wan't to go with OO, RoK or FoL. (You will also get a very neat Tier 2-unit for each of the religions) Build the temple for an additional priest-slot and run it (+ spread your religion to other cities if available and start to run priests there as well).
Now you face some hard choices (non of them strictly bad, all of them depending on in-game circumstances). Either you try to get trade to fetch some techs from other civs, or you try to get philosophy, then priesthood, getting way of the wicked for slavery might be worthwile even before priesthood (don't bother with mind stapling or arete yet. hidden paths might be worthwhile a bit earlier than those 2 but usually also only after! priesthood / trade. If you go with one of the later religions, especially in case of the empyrean trade might be the way better choice now.).
Depending on the number of prophets you have allready about the time you get philosphy you can do different highly interesting things with them. If you have 3 you might consider to spend one now either on founding the shrine or on bulbing priesthood or just firing the Altar 3 right away.
Founding the shrine gives some neat gold, mana (which can be highly interesting in its own right), bulbing priesthood gives some serious military bang (this is especially viable if you run OO, Early Cultists are a terrible thing to behold and are borderline impossible to counter that early on maps with some water / vs. costal cities. We are talking ~Turn 120-150 here. All on higher difficulties. Priest of Leaves with their kick-ass tigers also pack quite a punch for that part of the game). getting altar 3 sets you on the safe side and makes all your priests better + offers an additional priest slot for getting more GP + gives empire wide hapiness and makes all desciples build there into outof the box killing-machines.
Priesthood is the single most hefty bump in your power during such a game relative (especially if you run one of the 3 earlier religions) to the rest of the world. So after getting it you might want to stray abit to other thigs (like getting the national epic in your prime-priest city for double the GP, getting some other religions for additional temples / priest slots or some important economic techs.)
At that point in the game it should be no big problem anymore to get some greath priests over time more or less reliably.
Then its time to go into overdrive.
First you research religious law (in case of you running empyrean now comes your big moment with Chalid a one man army unmatched elsewere. Depending on situation in game you might also want to speed that one up with a bulb... You should be able to usually.).
That gives you Theocracy. The single most important civic for that strategy. it allows you to run unlimited priest specialists (i guess no explanation needed why this is important?) as well as +2 XP for all units build in a city with state-religion.
That means together with apprenticeship or another source of free xp (like a command post or the form of the titan) the desciple-units built in your altar city now start with 10 XP out of the Box. Thats 3 Levelups. Which means lots of diversity with your priests.
Also if you run order you get basilicas now. Neat building for huge empires. And social order civic. Few upkeep and hapiness issues from now on. (so here is the big payoff for the later religions.)
And last but not least a wonder which gives +1 Happiness for your continent if you can spare the hammers or have marble hooked up.
Now you should have your 4th GP (or the 5th if you got really lucky so you could spare one for other things) which will up the Altar another time giving all units visiting! it blessed promotion (+1 holy strength until next battle.) can be revisited after blessed is "lost".
If you have a spare non-greath prophet greath person (which is rather likely at that point) you might want to start your first golden age now (or second if you did manage to build the bone-palace or third if you did both of that and got an event fitting to your religion.).
Now you should go for fanaticism (the requirement for the most important altar, the 5th one. You should have the greath prophet before you reach fanaticism usually.). That improves all your priests to 3 hammers (as good as a Guild of Hammers-boosted engineer alone. And Guild of Hammers comes later usually. As comes guilds civic which whould allow for unlimited engineers.) + 1 Gold + 3 Priest GPP each (which should be more interesting to you now than a mine on grassland-hill / plains-hill) + up to 4 for culture from civics (caste system which might be very! worthwhile thanks to the resarch now. Also adds some research per priest as does the scolarship civic which you will get later on.) / wonders (hall of the kings, might also be viable) each + an additional happiness for your empire + another 2 XP (now giving +10 from the altar alone)
Also fanaticism offers a kickass unit for OO, Order and RoK (crusaders, stygean guards, paramanders. All 3 of them can use weapons i belive. So hook up that iron if you can. Paramanders need copper though i belive, the others need any metal.) which is solid Tier 3 with the enhancements desciples get now (+ they got improved further by your priests unless you run OO which has its own merits). No matter which Religion you do (except CoE or Veil of course.) + as well as some civ-heroes for some of the civs which might do good with the altar-strategy.
Now you might do whatever you want and see fit for 50 - 100 Turns (if you are neutral you might want to go for Druids, High-Priests, Paladins and Eidolons otherwise. Eidolons require you to be evil though so some switching at a later point might be in order). Your Economy and Power should be a force hard to match. So anything you might want you should be able to get.
Don't build the 6th altar yet though (gained at righteousness which also gives paladins so you might want it early if you run order.). Unless you like trouble. Its benefits are not that improtant anyways so it can wait (with a greath prophet in waiting to build it prior to the construction of the final altar.).
Then you should make your move to wrap up the game (as you see fit, won't last long until you get there). You have to get to omniscience now. (neutrals have a small edge here since they want commune with nature anyways for druids.) First you grab a sphere-tech or 2 (KotE should have been researched a long time ago, some adepts are allways worthwhile.). Divination should be one of those. Then go to sorcery (if you have gained another sage since the start of the game you should keep it for the turn you research sorcery). Bulb Arcane Lore with a Sage (which usually nets you another sage (unless you took a looong time or Amurites / Sheaim are in the game and did well too) which you can instantly use to bulb a small part of pass through the AEther.) then best go for pass through the Aether (unless you went mage heavy. Which is also possible by spreading the Ashen Veil to your altar-city which nets you insta-mages on building upgraded from savants. Then you might be more interested in Strength of Will) and build the nexus (which will help you in the ensuing endgame war for you beeing so daring to try achive godhood. The evil ones won't like that...

). Then build the tower of divination (you can very well pre-build that one in anticipation of researching the techs pre omniscience.), you'll need Sun, Mind, Spirit and Law Mana for that (2-3 of those usually are available from shrines + palace allready so not many nodes needed.), use it to bulb omniscience. Then build the 6th Altar and then start the final one.
Now that final thing costs 4000 Hammers which sounds like a real big lot. But! you likely won't need anything else much from sorcery on you can prepare and collect some money + a greath engineer or 2 (one can be obtained from machinery i belive). After getting omniscience you should switch to 100% Gold / 0% sience or something like that. After some 20 - 30 Turns the game should be yours. And should the other civs bother you, you should be able to utilize your army of high-powered desciples + nexus or archmages to greath effect (such games are also fun, sorts of, even though those units eat through superstacks like a lumbermill eats wood.)
The agnostic grigori were really good at that condition once but that got removed even though the altar is named after a group of people the grigori harbor (the luonnotar which is a grigori druid UU now.).
That might change again though (or the whole mechanics might be changed, there is some discussion going on currently about that toppic)
Currently though the Grigori have it the hardest aceive it. But still far from impossible thanks to their worldspell (+ the ritual gained at the tech needed for the final altar). They also get the least incentive since they profit the least from the altars and the prerequisite techs that are needed for the various stages of the altar.
PS: The illians may have the same problem i guess without the backstory part. But i haven't played them yet so i can't comment from experience there...
If you do it later on to wrap up a game, just switch to theocracy and run all out priests. Should be enough to get the measly 6 prophets you need in under 100 turns in a lategame-empire usually, or much faster with the right leaders + buildings + civics. (You don't get much of the benefits then but don't need such a focused strategy as well.

)
On tower-victory:
The tower victory is by far the easiest to explain. (Works best with civs which focus on arcane line of course or offer lots of synergy with it

.):
"Just" get some base mana (from uniqe features, shrines, palace, vasalls, colonies, civs you subdued into captiualtion or via trade, other sources?) sorcery and some base nodes (2 if you are really lucky and the situation permits, 3 should do relatively safely).
In that strategy its very worthwhile to found all religions you can fetch and don't have the mana easily from other sources (best focus on those which complete a set of 1 base prerequisite mana for each of the towers first, then try to get another set or one complete tower.)
Then after getting sorcery bulb arcane lore (with a sage, get another one for free, you should be guaranteed that one if you are Sheiam or Amurites) while get a metamagic node up and some mages promoted to Metamagic 2 (+ some spare adepts with Metamagic 1, can still promote later if needed). 5 Metamagic 2+ casters should suffice but 15 have their merits as well if you go mage-heavy empire switching those nodes as you see fit at the blink of an eye, Then reset those nodes and build the towers. Grab the tower of divination as early as you can after getting arcane lore. Slingshot to Strength of Will and wreak some havok with your Archmages + Liches (don't forget to optimize your mana before upgrading your adepts to mages to archmages.)
Then if you are ready (better safe some gold / engineers beforehand) start the 4000 hammer (dé ja vû?

) Tower of Mastery and win the game (you just need the towers build not all the mana.)
Thats usually the fastest one to wrap up a late game you are bored with if! you have 3 nodes handy and didn't 'waste' all 3 before getting sorcery for metamagic (not always the case) are powerful enough (also not always the case in higher difficulties).
But as a strategy in itself its less stable and offers much less on its own in comparison to the altar. Which offers a complete Strategy for a game. Also ToM has the drawback that all civs will declare war on you if you start to build it, not just the evil ones. (no one likes wannabe world-dominators.

)
So you got solid victory conditions right here for all tastes of builders:
A challenge which has to be well planned and executed from the start and doesn't support or win on itself in case of cultural (which is a good one for diplo and peace-heavy mass-hugger 'we are all friends' games. And the single best one there. Since utterly foolproof if you get the diplo set up right),
a game encompassing strategy / minigame in case of altar (evil ones excluded. Sorry... Those have another "goal". Armageddon. Also fun. For them at least. Mostly... Read more in the strategy-and tips forum.),
and one to wrap up games you are bored with fast in case of ToM (shouldn't last more than about 50 turns from decision to execution).
Religious can! also be a builder game but only works on smaller maps with a lot of luck in my experience (and by that i mean my experience with conditions were it whould be possible, not actual wins).
You can use inquisition in foreign cities as well. But they must share your State-religion for you to be allowed to. And you need open borders of course.

(Bribing them might work though if your relations with them are decent. But you better hurry. Lest them switch back.)
Usually its a wormonger condition though bash the nonbelivers into oblivion, then purge all the others.
If you whould coun't all religions you founded and have a shrine for it whould become way to easy. Its borderline a cakewalk to found + conquer about 5 if you want it... (and thats in immortal with certain civs.) founding 7 all by yourselves is possible if quite unlikely.
I personally rarely if ever end a game in conquest (save for the odd barbs take over game.) or seldom if a bit more often in domination, at least on smaller maps (the last place though is adamantly reserved for religious. Only have one there and it was my fastest ever. On a duel map me "vs." Grigori.

wanted to see the movie for religious...

).
Most of my games (since i like bigger maps standart +, usually large) end in ToM, Altar or Cultural (most pre Turn 500, vast majority around Turn 400 normal speed.).
And its still a lot of fun. So the builder- and turtle-victories can't be all that bad.