I'm with PS--even though I never played III, I highly recommend IV. My reasoning is as follows: III has a very well-known exploit which was not plugged until IV, namely, Rapid Expansion (more commonly referred to as REX). The secret of the game was to build as many cities as fast as you could in the early game, claiming as much land as possible. In IV, this exploit no longer works; city maintenance costs will run your economy into the ground if you try it. Thus, you have a more challenging game than before.
I don't want to run down III, because it has its fans, but hey, I used to love Civ II, but I don't play it anymore either. (I tried to the other day, because my Civ IV computer is out of commission; but you can't go back, I found!) Times change and the game gets better.