Civsassin
Immortal
Let's look at Civ 3/4. How were you able to beat deity level AI?
In Civ 3 you had to use a combination of really good MM of your cities, pointy stick research, playing the diplomatic game well (use trade slingshots, getting alliances for wars) and a solid warmonger part where you would use your armies well.
In Civ 4 you had to really plan properly where to build cities (sites actually mattered a lot), maybe start an early rush against a neighbor, play the religious game well, decide for a specialist or cottage economy etc etc. In fact in Civ 4 you had so many options that the game was somewhat overwhelming.
Overall, Civ 3/4 also provided you with some sort of pride looking at your empire and some top cities you had (looking at the size, hammers per turn, science etc)
I don't think it is fair to compare Civ V to either Civ III or Civ IV. Consider that both of those games had multiple patches and expansion packs. Civ IV vanilla was a fairly simple game also. Many of the features were added in expansions. Expansion packs to Civ V will add new civilizations, new victory conditions, new units, new game mechanics (religion, espionage, or similar), new scenarios, and improvements to game play. If you don't like Civ V in its current form, you can stick with one of its predecessors until it is patched and/or expanded to your liking. With so many fundamental changes to Civ V, it is no wonder, and admirable, that Firaxis is learning from and responding to fan feedback.