Stepping off the boat in Tallinn, the capital of Estonia, you feel you've traveled a long way culturally from Finland. It's a mix of east and west. Tallinn's Nordic Lutheran culture and language connect it with Stockholm and Helsinki. But two centuries of Tsarist Russian rule and nearly 50 years as part of the Soviet Union have blended in a distinctly Russian flavor.

Finns and Estonians share a similar history — first Swedish domination, then Russian, then independence after World War I. Until 1940, the Estonians were about as affluent as the Finns. But then Estonia was gobbled up by an expanding Soviet Empire and spent the decades after WWII under communism. When the USSR fell, Estonia regained its freedom and in 2004 it joined the European Union.

Tallinn has modernized at an astounding rate since the fall of the Soviet Union. Its business district shines with the same glass and steel gleam you'll find in any modern city. Yet nearby are the rugged and fully intact medieval walls and the town within these ramparts has a beautifully preserved Old World ambience. Among medieval cities in the north of Europe, none are as well-preserved as Tallinn.

The Town Hall Square was a marketplace through the centuries. It’s fine old buildings are a reminder that Tallinn was once an important medieval trading center. Today it's a touristy scene full of people just having fun.

Through the season each mid-day, cruise ship groups congest the center as they blitz the town in the care of local guides.

Like many tourist zones, Tallinn's is a commercial gauntlet. Here, there's a hokey Torture Museum, strolling Russian dolls, medieval theme restaurants complete with touts, and enthusiastic hawkers of ye lode taste treats.

But just a couple blocks away is, for me, the real attraction of Tallinn — work-a-day locals enjoying real freedom and better economic times: Still-ramshackle courtyards host inviting cafes. Bistros serve organic cuisine in a chic patina of old-world-meets new.

And just outside the walls, it seems there's no tourism at all. Under towering ramparts, the former moat is now a park… perfect for a warm afternoon stroll.

In the 15th century, Tallinn consisted of two feuding medieval towns: The upper town — on a hill, called Toompea — is from where the country of Estonia has long been ruled. The lower town was an independent city. As a member of the Hanseatic Trading League, it was an economic power here in the Baltic world.

This thriving port town was filled with mostly German merchants who hired Estonians to do their menial labor. The Old town feels Germanic with streets lined by the fancy facades of those 15th century big shot merchants.

This merchant's home functioned as his warehouse and office as well. Its elaborately carved door evokes the wealth of Tallinn's business class in those days.

Stairs lead from the lower old town into the fortified upper town, Toompea. Climbing into Estonia's historic capital, it's clear the architecture tells a story.

Neighboring Russia has always loomed large and threatening over little Estonia. The Alexander Nevsky Cathedral was built here by Russians in 1900. While a beautiful building, most Estonians don't like this church.

It was built to face the Estonian parliament building, clearly designed to flex Russian cultural muscles during a period of Estonian national revival. This tower survives from the original Toompea castle. Nicknamed Tall Hermann, it's a powerful symbol here.

For 50 years, throughout the Cold War, Estonian flags were hidden away and the Soviet flag flew from atop this tower. Then, as the USSR was unraveling, Estonians proudly and defiantly replaced the red Soviet flag with their own.

Today, while Toompea is filled with Estonian government buildings, it's also simply a pleasant place to stroll and enjoy some romantic viewpoints.

Russia's influence over Estonia goes back long before the Soviet Union. When Russia took over Estonia in 1710, Tsar Peter the Great built the stately Kadriorg Palace for his Czarina, Catherine. The Czarina's private garden is now Tallinn's finest public park. The standard progression as divine monarchies give way to modern democracies and the former guard house now serves coffee to commoners.

The leading sight within the park is the KuMu Art Museum, Estonia's striking national gallery, opened with pride and fanfare in 2006.

While Estonian art evolved in step with the rest of Europe — it was also shaped along the way by the nation's history. For instance, nineteenth century Romanticism was the artistic style of Estonia's aristocratic German landlords who enjoyed art featuring idyllic Estonian peasant women in folk costumes and idealized settings. Local artists continued to paint in sync with European styles from Impressionism through Cubism and so on.

But Estonian art parted ways with Western Europe after the Soviet take-over in 1945 which brought the end of artistic freedom. The Soviets insisted on one kind of art: Social Realism. This was beyond censorship. Art had to actively promote the Communist struggle. The Estonian artists' union was forced to renounce individual expression and be re-educated. The Stalinist formula: "National in style but socialist in content." Painters produced themes like this, titled "Excellent Young Communist Workers."

Industry was celebrated. Mining was big in Estonia. So miners were portrayed as heroes, marching like soldiers to their glorious work.

Soviet women were shown not as the idyllic cliché of traditional motherhood but as strong laborers, working side-by-side with men. They were entirely engaged in the quest to reach the communist ideal. Here, a woman oversees the bolstering of agricultural production.

Posters were a natural fit for Social Realism. They could be mass produced. They generally came with a proclamation — this one reads, "It is good to work hard and buy government bonds." And they carried the propaganda message to every corner of society.

In the 1960s things began to change. Many Estonian artists took a more independent and avant-garde approach, injecting hints of social commentary into their work. This angered Khrushchev and many of these artists ended up in Siberia.

But as the Soviets would eventually learn, change was unstoppable. Western ideals began to infiltrate. Estonia was the only part of the USSR where pop art was recognized. Painters featured utopian scenes viewed through the eyes of alienated urbanites… Artists flirted with the psychedelic as a new generation came of age.

Local guide Mati Rumessen, who grew up under Communism and did his military service as a driver in the Soviet army, is joining me to help us better understand the challenges of living fifty years under the Soviets.

Mati: I remember when Viru hotel was only skyscraper in the city and because KGB was very curious of every word spoken by foreign tourists, we had a local joke that the house was built from Soviet wonder material so called micro-concrete which would be 60% concrete and about 40% of microphones.

Tallinn's vast and blocky suburb of Lasnamae, with about 90,000 apartment flats, dates back to Communist times. The Soviets attempted to Russify Estonia by planting or moving people into this country. Because of that about a quarter of all Tallinners are ethnic Russians.

And, as is clear at this predominantly Russian market, the plantation of people — as it seems is always the case when governments move people for political purposes — leaves a poorer and struggling ethnic minority and their reluctance to assimilate leaves long term social challenges.

Nearby is the stage from where the people of Estonia gathered to demand their independence. The Song Festival Grounds, which hosts massive choral festivals, is a uniquely Estonian institution. This is a national monument because of the stirring role it played in Estonia's fight for independence.

With only a million people, lodged between Russia and Germany, and without a strong military, Estonians asserted themselves with song… They say being together and singing together was their power.

Rick: 300,000 Estonians gathering here to sing together.
Mati: Yes, one day in 1988, one third of Estonian nation gathered here to sing. To sing about the freedom, about the independence, to show to the rest of the world and especially to the Soviet side that we are tired to be one part of the Soviet system and as we can see now, almost 20 years later that it was successful.

Tallinn's Museum of the Occupation rounds out the story. Suitcases are a reminder of people who fled the country leaving everything behind. Displays show how Russians managed to keep the Estonians in line. Surveillance was a part of daily life. Prison doors evoke the countless lives lost in detention and deportation. And the communist leaders who once lorded over the Estonian people are now in the basement guarding the toilets.

With freedom, Tallinn has joined Helsinki as a vibrant and welcoming destination. Each has a unique charm: Helsinki with its thriving esplanade, striking neo-classical design, and island escapes. And Tallinn with its medieval old town witnessing the emergence of a new prosperity.