Two leaders for Norway:
Olav Trygvasson, warfaring king, founder of the city of Trondheim, ruled in the 9th century.
Magnus lagabøte Håkonsson, peaceful lawmaker (lagabøte meaning "revisor of laws") and great diplomat, ruled in the 12th century, born in the city of Tønsberg, recided and died in the city of Bergen. Wrote laws for the country (these laws later adapted in Iceland, Shetland, Hebredees and Greenland) as well as special city laws. Sold the Hebredees and the Isle of Man to Scotland in 1266 in the Perth-treaty. Signed the Winchester-treaty with Henry III. Managed through diplomacy to avoid war with Denmark.
And the vikings should have not only the berserker as a special unit, but also a special galley - a dragonhead longboat (strong oceansailing vessels, carried a lot of vikings and their lute), sadly missing in current Viking scenario.
The other nation I would like to see:
The Mapuche Nation (of Chile and Argentina)
They were the only indiginous people of South America that stood up to Spain, and were actually granted a letter of independence.
Special unit: Toqui (axe-bearer).
Read up on them here:
http://www.mapuche-nation.org/english/main/feature/m_nation.htm
or here:
http://en.wikipedia.org/wiki/Mapuche
to find special traits for them.
A special kind of hospital would be nice, as they had/have some great healers, or a special court of law (they had/have a very orginized society). Or maybe forests yielding more labor, as their "national tree" is the Araucana, the Monkey Puzzle tree. Or that last one could be made to replace levee/dike - grow (build) an Araucana and forests/timbermills/national parks yield more labor.
They could also be used as an introduction of a new religoin - shamanism, with a Machi (spiritual leaders that function as: witch-doctors (curandero), and/or herbalists, religious authorities, and consultants) as missionary.