Scandinavia, Celts and the Byzantines!
Scandinavia is still a unique place, and it has a long history in Europe: the Viking raids, the Kalmar Union, the thirty years' war and the great Swedish nation that followed, which ranged from Norway to Prussia, Poland and Estland. Leaders could be Gustav Adolf "the Snow King" (a great Swedish king) and perhaps Erik the Red (a Norwegian adventurer who founded Greenland).
Similarly, although the Celtic "empire" didn't last long, it did range from one end of Europe to another.
The Byzantines have always had a spot in my heart. I just love the history and the unique culture of the eastern Roman state. I think they were poorly presented in CivIII, but now there might be a chance to remedy that.
I also miss the Babylonians. Although, I have to admit that Persia does a good job at representing most Middle-Eastern civilizations. You can easily think that they represent Assyrians, Sumerians and Babylonians. But there's nothing that can represent the Norsemen. There might be a spot for Turks/Ottomans, though.
An evil period in history, but an interesting twist on gameplay
Exploitation of the masses was not invented by the Europeans. The European leaders only replaced the existing tyrants with despots of their own.
Perchance civilized nations should have taken a different approach than the age-old exploitation of those who are weaker and technologically backward, but that was the Zeitgeist then (and I can't say it has passed). Similarly, slavery was a part of the Zeitgeist, when thousands upon thousands of them were shipped from Africa to the United States of America. Certainly we see these periods as "evil", but that's just our modern, Western morals speaking.
To a slave, a tyrant is a tyrant, no matter what culture or race he represents.