Caesar.: Beyond the Sword is the full Civ4 experience, and it's considered by many players the epitome of the Civilization series.
However, when you're looking for a change, make sure to check the scenarios that came with the Warlords expansion and that can't be accessed through Beyond the Sword. They are very fun and I can't recommend them enough (you can even play as the barbarians).
Indeed. Also, Desert War (WWII in Northern Africa and the Mediterranean scenario) came with the base game, and IIRC it can only be accessed from there. It is worth a shot--pun intended ;-)