I don't really know where to start with, so I'll start by what I found most disgusting: the religion system. I remember reading a Sid Meier's interview in which he said that he changed civilization from a real time strategy game that you would direct the cities production and watch them grow to the turn based classic everyone knows and loves 1 week before the global shipping date of the final game (for the younger boys and girls out there, physical distribution of software was the rule in a pre or bad internet world), and in that same interview he stated something like "adding too much content can make a game too complicated, and simpler can be better". These two statements really marked me, "it is never too late to change a game" and "simpler can be better". That's not the case in civ5's religious system introduced with G&K. Religion turned into some sort of secondary money that provides minor bonuses (although it can be used to produce some really powerful combinations, depending on the case), while it worked very interessantely as a major player in civ4 (what makes sense, to be honest).
Religion was over-emphasised in Civ V, I suspect, largely as an effort to respond to Civ fans' comments here and elsewhere, as they missed the importance it could have in Civ IV.
Let's make no bones about it: Civ IV handled religion very badly. Its value in a given game was largely contingent on variables outside the player's control - the identity of nearby civs and the value they place on religion, how many religions were founded and how many were able to spread to you. Temples were important early in the game, but not available early in the game unless you rushed specific techs before the AI got there.
Civ V has work that needs doing in terms of balancing both the game and diplomatic effects of religion (the former should be toned down and some of the more excessive bonuses, such as Tithe, either removed or given higher priority by the AI; the latter somewhat more relevant). But as is quite common in Civ V vs. the earlier games, Civ V provides a superior framework to work with (the same is the case with trade and with diplomacy, and possibly with combat) even if the execution can be more miss than hit. Removing the link between religion and technology was a particularly good move.
Adding extra options is not the same as adding extra complexity; in interviews given re Civ V, Sid has said - just as you've noted he said in the past - that the complexity of Civ games should remain about where it is, and he's contended that Civ V is no more involved in that regard than the previous games. There's some truth to this - an abundance of options can appear dauntingly complex when you're first learning to play (a friend has been turned off Beyond Earth by previews of the tech web on this basis), but religion is basically an extra set of options that co-opts the existing structure of policy or tech decision-making - the player already knows how the core system functions.
Even the more recent possibility of founding 'protestatism' before 'orthodoxy' or 'catholicism' makes me feel stupid. I understand that is a way to try to balance some completely useless flavour that the civilizations have (favorite religion), but it just makes absolutely no sense, even for a game like civilization.
This is true - they'd have been better off not using pre-named religions, but they needed a set of icons and I believe that - once again - this was a specific player-requested feature.
As the immersion of the game bases itself on building alternate timelines, doesn't it make more sense to scrap out the favorite religion flavour than to actually break one religion into 3, one of them making absolutely no sense without the existence of another one for about 1.5 thousand years? Turning faith into a resource also makes the religion reasonably too controlable, and it shouldn't be. Religiosity flows more freely, and civilization5 makes it too square, it just doesn't seem to fit in the game.
Civ V is very much more deterministic across the board than previous games. There are no more random events, for example. In terms of pure gameplay, this improves the strategic element, but it can also end up with games becoming somewhat too static.
Civ IV rather got the worst of both worlds in that regard - a strategy game should either promote problem-solving to find the 'best' strategies (which results in static, build-order-focused play of the sort you find in Civ V), or it should present you with environmental challenges that vary with each playthrough and to which you have to adapt.
Civ IV allowed the environment to exert a major impact on gameplay with random events and only slightly less random religion, however at the same time it was fundamentally a build-order game and didn't actually give you any tools that let you adapt to events to your advantage. As you say, you had very little control over religion, and you couldn't invite one in or choose a state religion unless that religion had randomly spread to you (unless you'd founded it). Random events just popped up and had effects, with nothing you could do to mitigate them or improve the likelihood of benefitting from them.
Given a choice, I'd prefer a game with environmental challenges and tools to adapt to them. But given the choice between a static, build-order game with absolute player control - like Civ V - and the same basic game with uncontrollable random events - like Civ IV - I'd go with Civ V.
The combat system. Unit stacking could really spoil the fun of the game sometimes, but the way the problem was solved isn't good. The overvaluation of the units in civilization5 makes it boring. The units move too fast for the board. The overall feeling is that there is less space in the board with the 3 hexes city range and with the multiple city states. And even though there is less space, the units are able to move faster and they might take multiple turns to die, which also tends to kind of overcrowd the game map even with fewer units if in comparison to other civ games. The AI doesn't know how to properly use ranged combat, it tends to stack multiple ranged units in nearby hexes and to target not the biggest potential threat to them, but an unit that will actually die if fired at, even if they all die on the following turn. The combination of ranged attacks with the 2 hexes default move also doesn't feel good, it adds too much flexibility to some units that shouldn't be too flexible. I gotta admit that that I really liked the hit points and firepower systems of the cities, though. Finally early sieging feels like what it should.
There are several issues here. As you rightly point out, when it's commonly complained that the AI can't use 1UPT, what is meant is that the AI can't handle ranged combat. I'd hope that future games restrict ranged combat type effects to siege and bombardment units (a la Civ IV). That alone would streamline the game.
I find I prefer Civ V's unit production rates and unit survival to earlier Civ games, merely because stacks were tedious mostly because of the numbers involved and because having to spam units every so often to keep up in the military race was excessively dull and strategically very limiting. You're right about map crowding, however. Some form of stacking might work better if unit production rates follow Civ V rather than the earlier games.
Gold. I like the fact that gold is more important in civ5, but it shouldn't be directly generated as a resource, it should be generated as an outcome of exploring other resources, and this shortcut civ5 has taken, although valid and theoretically interesting, is also dangerous. It is dangerous because it also to an overweighting of gold. Gold can surely buy pretty much anything, as long as it is for sale. And it can't do miracles (which it pretty much does in civ5, much more than faith). The old system of commerce and direction to the investments it allowed seemed more realistic than the new too plain budget system, something should be worked out in between those two. I also like the fact that science is now an independent resource per se, but this indepence is, too, exaggerated - it makes sense that a ruler, specially a godlike one, such as is the case of civ, should be able to direct its investment in science (if any).
Gold is something that has changed quite a bit over Civ V's lifetime. It's now in a pretty good place as far as how it's generated is concerned - it is now a production resource generated mostly from trade rather than harvested as 'commerce' sitting in the landscape, and having the resource generated in a fundamentally different way from the others is a great move. I'd like to see this further developed - remove gold from resource tiles, reduce base gold output from trade, and increase the weighting resources (and perhaps specific resources) add to trade routes. Trading post and custom house improvements could add to the value of trade routes that pass through them, again instead of producing output directly from tiles.
In terms of gold spending, this is I think another area where Civ V overcompensated for a weakness in the previous games. Civ V as it is is balanced around being able to buy anything and everything with gold, but hopefully Civ VI will tone it down somewhat and either limit what money can buy or increase the relative cost of purchases.
Also, Civ V appears to suffer in your eyes less for being what it is than for your greater awareness of the competition. Do you find Civ IV as engaging having played Paradox games, or are you enjoying it with a nostalgia you obviously can't have for a game that's contemporary with the Paradox titles?