Civ 5 does the difficulty tiers a lot better than Civ 6, they feel more gradual and I can still have an enjoyable game all the way up to Emperor and end up accomplishing most of the goals I wanted to get done, but in Civ 6 once I go past Prince, I can't even build Stonehenge or establish a religion at all,
Stonehenge is hard to get at the highest difficulties, but not impossible - I'd be surprised if it's not feasible on Emperor, as long as Astrology is one of your first 3-4 techs. Bear in mind that you'll often need to chop woodland or stone to finish it. I doubt however that it is usually worth the effort compared with naturally earning a Great Prophet, for which you want The Oracle and a beeline to Political Philosophy once you have Mysticism, for the Prophet card. Divine Spark can also help as your pantheon.
This route has the advantage that the Oracle and an early government are simply generally good for any strategy, and while Divine Spark isn't as good as specialised pantheons that fit your starting position better it's never bad to have. So even if you miss on a prophet you've started on a good route, while losing out on Stonehenge can set you back heavily and it's not a particularly special long-term buff anyway.
That said, I don't much like religion in Civ VI and usually do without it altogether on Deity - the religious combat and conversion system is excessively tedious, made worse by AI religion spam behaviour. I mostly use it to get martyred apostles if I want relics in quantity. I find it a core feature of the game the game is usually better without. Religious victory remains the one I've never got, mostly because I haven't really tried for it.
this, along with a bunch of other nitpicks like capitals being spawned too close to each other, the AI typically settling new cities towards the direction of the human player,
I suspect the idea is to promote reasons for conflict in the early game. You generally want to be in a position to either capture early cities if the AI settles near you (or occasionally city-states, but aside from militaristic states you usually want CS bonuses early in the game more than you want the city), or better yet to capture an AI's settler before it turns into a city.
barbarian camps chain-spawning cavalry even though crazy barbarians option isnt turned on,
I don't like the barbarian system in Civ VI at all - certain map types, like Inland Sea, seem to have greater incidence of barbarian activity that makes the game a slog to play. That said I don't find myself coming across horsemen camps often.
the continents seeming smaller yet real-estate being more important
I don't think I've noticed this - the maps feel relatively larger to me than in Civ V. There seems a fairly widespread opinion that map generation in Civ VI is problematic, though - basic elements such as the non-random distribution of resources (two luxuries per continent - which makes trading luxuries impossible on the smallest maps, where only one continent exists, for instance) and what we've recently learned is the allocation of space to each civ either are poorly-conceived or appear to work inconsistently in practice.
I haven't had the trouble you have with the game, but my best advice would be to remain flexible. I generally like to play reasonably peacefully at least in the early game, but in one recent game forward-settling by Georgia in one direction and a cavalry barbarian camp in the other completely prevented me from expanding peacefully at the start of the game, and I was slowed further by a starting position low on production next to tundra. So I changed tack, focused entirely on military, and took out the Georgian cities. That's a definite departure from my usual plan of building a couple of units to defend and settling ASAP..
You don't need to start seriously thinking about your route to victory until past turn 100 (and even then you can transition quite late after that at need), so losing access to religion isn't vital and shouldn't set you back too far. Civ VI can feel difficult in the early game when you're getting established - but it's extremely forgiving once you get to the mid and late game, allowing you to go for basically any victory with a late start. I'm routinely at or near the bottom of the civ rankings as late as turn 200 or so and can still win on Deity.
