Civilization IV is part of the Civilization franchise, and a franchise can usually only be successful if it makes conservatively changes between iterations. So Civ4 is not extremely different from Civ3 -- it will be a conservative sequel. According to Soren Johnson, a good rule of thumb for a franchise is "1/3 old, 1/3 improved, 1/3 new". He believes that the best way to improve on Civ3 is to choose a focus and really improve the game in only a single (or a few) area(s), rather than trying to change a little bit of everything. That doesn't mean that Civ4 will play the same as Civ3, while the essence of previous games has remained, many details have changed and the step from Civ3 to Civ4 is the biggest and most ambitious one the series has made to date.
Soren also points out that genres/franchises that get increasingly complex tend to die out as they become accessible only for the real hard-core fans, no longer for casual gamers (example: flight simulator games). Soren thinks that RTS games are heading in this direction. To prevent Civilization from making the same mistake, Civ4 will not be considerably more complex or bigger than Civ3 -- only different. Also, it will aim at a slightly different fan-base than previous Civ games, though it should still appeal to (most) veterans as well.
One of the key phrases for Civ4 will be "Simplify, simplify, simplify", which means as much as streamlining the existing gameplay where possible. Making the game concentrate on the main map rather than forcing a player to switch between many different screens is one way to do this. Cutting down on things like corruption, Building maintenance, pollution, etc is another.
Another important thing for the game is "accessibility". By the words of Senior Producer Barry Caudill, Firaxis aims to make Civ4 the most accessible version of Civ to date -- in the widest sense of the word: an accessible user-interface (with lots of tool tips and pop-up help), accessibility for new players with a top-notch tutorial, accessible gameplay by eliminating micromanagement for its own sake (e.g. getting rid of pollution, building maintenance, etc) and finally an unprecedented level of access for mod/scenario makers [see Modding]. Firaxis hopes all this accessibility will help attract a new audience to the game who may never have played any Civ-type game before.
Civilization IV will "borrow" successful elements from other strategy games. Things like espionage, wonder movies, and the firepower-like damage model will remind veteran players of Civ2. The Civics system is very similar to SMAC, while Religions and the multitude of terrain Improvements like the Call to Power series. Religion, Civics and Leaders all function not unlike the Europa Universalis games. The unique bonuses and roles in the combat system have a lot in common with Rise of Nations while the User Interface is reminiscent of RTS games in general and the Promotions system is similar to RPG games. But of course, many aspects of the game, such as Culture, unique Civs, Wonders, Resources, Diplomacy, etc are based on Civ3. And finally some other systems, like Health, technological OR-gates and Great People, are more or less unique and new to the genre.
The AI in an important area of focus for the Firaxis design team in general and Soren Johnson in particular. The AI is designed to cheat less than it did in Civ3, while still being a challenge to play against. City Governors are also considerably improved, so that city management both for AI and beginning human players can be at a competitive level. Finally, giving the different AI leaders different personalities is also an important area of focus: Gandhi is generous to weak players, while Genghis Khan will shy away from diplomacy and dislike anyone who's not an aggressive warmonger like himself. AI players also have distinct preferences when it comes to Religions and Civics. They get along better with players that share their favourites and try to convert/reform players that do not.
Finally, Soren notes that Civ3 was under too much time-pressure to really make it what Firaxis wanted it to be in terms of MP, modding, etc, but he is confident that Civ4 will make significant improvements in this respect: "Civ4 is very much a maturation of the franchise".