I'm sure that there's a lot of individual taste in how replayable a given game is. For me, GC2 has been insanely good in that regard, not least because the expansion packs add major new aspects to the game. The options are numerous and the computer players were the best I'd seen to start with and have been getting steadily better.

When you play on an immense map with tight clusters and don't max out the habitable systems, you can create enough space for all the different AI types to do their thing for a while. And that is never quite the same thing twice. You can see some evidence of that just in posts around here, where players describing similar strategies and map preferences have wildly different ideas about what the "most dangerous" computer civ might be. Then there's the role of events and mega-events, which can add even more variety if you like to have random stuff in your 4X.

I don't mess with the editors or the campaigns, which is in part a reflection of how good the main game has been at holding my playtime attention.

Re tech trees, keep in mind that they are part of the last expansion, Twilight of the Arnor. From what I've seen, the old-hand consensus around here about folks starting with a multipack is to begin with the base game, Dark Avatar. But whenever you do choose to play TA, IMO, the impact of the different tech trees on map variety is fairly small unless you disable Tech Trading. With Tech Trading off and an immense map with some big gaps between home territories, things can look very different from map to map depending on which civ gets the most beneficial set of initial colonies and resource mines. Sometimes, you might barely make contact with the last few major players before they're destroyed by rivals with territories between you. Other times, like on my current map, you can get past 300 turns with all 9 majors and 8 minors still intact. I'm pretty sure that's a first for me.