(note: I use the AI+ mod, which adjusts AI prioritizations and typically slows them down a little bit with wonder-building and Deity++, which reduces AI bonuses at start and increases all yield bonuses; this may either delay or speed up wonders, I haven't played enough with it yet to say for sure)
In the game I am currently playing, I got Poland, started with
five stone (which actually gets buffed by TCS's Omnibus mod, which changes Holy Sites to grant +2 faith to stone, wine and incense for the city) as well as several +3 mountain adjacency bonus spots for holy sites, so it was immediately quite clear that I would go for a religious victory. Playing Emperor, I actually managed to get Stonehenge, which is also delayed a bit as you (also courtesy of TCS's Omnibus mod) need to research Pottery before being able to research Astrology. So I don't know how much my mods mess with it, but I actually managed to get Stonehenge on Emperor.
For the rest, if you really want a wonder, I feel like it is about always possible to get it simply through beelining the tech and instantly going for it. I do feel, though, like many wonders just aren't worth the hammers, as they tend to take 30 turns in good production cities when they become available. Most of the wonders I build are because I scoop them up from an era or two back. An exception to that is the Colloseum, which can just give you the equivalent of 5 luxery resources (plus a bit) if you manage to have it cover 7 cities.
I've done a lot of testing involving wonders for modding purposes, and while I play on lower difficulties (because it's easier to test there), my observation tends to be that the AI will heavily prioritize religious wonders. The early wonders also tend to go quick, but strangely enough, not the Colosseum. It usually sticks around for a long time. I can't comment as effectively on later-era wonders since usually by that point in test games I've so far outstripped the AI in tech/culture they don't compete for them.
I agree that Colloseum should be gone far earlier because it's so strong, but I can also explain why it doesn't: AI
sometimes often has a weird district prioritisation, and part of that is that they barely build any entertainment districts, so they just don't have any tiles they can build the Colloseum.