From the point of storytelling, I would (cautiosly) argue for Civ IV, because of somewhat livelier diplomatic interaction and bigger choice of actions.
Religion plays much bigger role in IV's diplomacy than in V. You may find yourself at the crossroads of which religious camp to pick. You may have to wait with your decision, to drop one religion in favour of another because of your own opportunistic plans or in fear of impending doom. In V religion is more of a nice tool for your internal purposes and hardly ever a casus belli.
The vassal state system. It may have its flaws, but it certainly adds to the storytelling. Clashes between two or three great alliances have always been a source of inspiration for storytellers of all kinds. One moment you may face a seemingly monolithic alliance with little options for you, the next some peacevassal renounces its master's protection and opens a breach for you to step in and strengthen your position. Or vice versa a hopeful friend, whom you courted in every possible way, peacefully vassals to your rival, and next thing you know they're both knocking on your gate with a very big club. In Civ V the lines of the great divide between groups of countries are drawn after ideologies come into play, but for me it feels a bit forced.
A game of Civ IV is probably more manoeuvrable, if you can say so, you can juggle civics, research and money sliders, etc., and the one of CiV is more rigid, with policies you set your course for good. And more often than not it will take longer.
As for the lushness, Civ V is an eye candy, true, but now there are some nice graphical mods for Civ IV, Blue Marble, etc. which improve things to some extent.
And for conclusion, as some people already mentioned, the big sales season is approaching. Are you sure you won't be able to pick both of 'em?