I started with Civ 3, and imho if you like Civ 3 but didn't like the corruption/waste or pollution (and thought veterans should be stronger) then I think you should give Civ IV a shot.
Especially with FFH mod.
however, yea ... I to am skipping on Civ V for now, I no longer believe a game is worth buying until it is at least a year old.
I found the Civ3 editor corrected the excessive corruption/waste problem and made it a useful part of the game, and I liked the pollution. I also thought veterans were over powered in the regular game, but one could make veterans any way they wanted with the editor, even make them the same as conscripts or 10x more powerful. The way combat was modeled in Civ3 was a 100x better than the garbage in Civ4 with its single O/D factor and cheesy specials.
I initially tried the Civ4 demo when the game came out. My first impression is that this was a kid's game. You had animals running around knocking off units (lions and tigers and bears - OH MY!!! ) which was very silly, childish and stupid. The previous barbarians were a much better idea. I liked how the game starts off announcing you had this group of nomadic hunter-gatherers and then after forming your first town, you get to research - hunting. Cheese. Later I got a chance to play the full game at a friend's place. He had the expansions, also. And I found the Civ4 cheese only got more ripe. You see, I look at the civ series as an all round strategy game, involving units interacting with each other, science & development, economics, the works. A little bit of everything that goes into making civilizations. In Civ4, they essentially removed the units from the equation by making them so basic. You had all these complicated other dynamics, but the units were an afterthought. Half the game for me is building the civilization, the other is messing around with the units. So with Civ4, they took away half the fun for me right there. But that was only part of the problems I had with getting into the game. The other was the way the development worked. There were too many steps that didn't add to game play. They only made the game more tedious. They were not modeled very realistically, either, in fact, realism wise, Civ4 was less realistic that Civ3 in its mechanics. An example would be the religion in Civ4. Pure limburger cheese, that. It added another layer of tedium, but in no way resembled religion or how it affected things in real history.
I came away from playing the game comparing it to MOO3 - way too much tedious "busy work", no immersion, and no real enjoyment of the game. They took away the wrong things and added too much "accounting" work, it felt like playing a combination of one of the sims (which I find really boring) and doing my taxes (no need to elaborate on that). It didn't feel like I was playing a strategy game about civilizations. It felt more like a console game where the game play was an aspect that got left out.