First, ideas for improving Frozen/Noway. Then, a quick rant.
When it comes to enhancing Frozen Ever After, stitchcastle hit the nail on the head. The attraction should take place in a massive, ornate ice palace located on the edge of Fantasyland. I wouldn't build Arendelle (I'm tired of fantasy villages; you've seen one you've seen them all), but would instead create a Winter Wonderland mini-area, maybe including an ice cavern restaurant and some sort of a snow-themed flat ride...ooh or a toboggan family coaster. Wandering Oaken's would be near by as well. As for the ride itself? Sled vehicles are obvious (although I'm not opposed to a boat ride...melting ice?), and incorporating scenes inspired by Marc Davis' Snow Palace, including dancing ice fairies, sleeping polar bears, penguins racing us downhill on their bellies, etc. should be a given.
In Norway, I'd like to see an attraction similar to Sinbad's Storybook Journey, featuring the Legend of Harald Fairhair. A viking warrior, Harald is noted for uniting several area viking tribes and becoming the very first Viking King of Norway. What's so amazing about his story though, isn't what he achieved, but why he did so. Harald was head-over-heels in love with a Viking princess who refused to give her hand in marriage until he was king over all the tribes of Norway. So, to prove his love, he began an expedition to unite the tribes of Noway into a single kingdom, and until that task was accomplished, vowed not to cut nor comb his hair.
^^That's the actual true legend of the formation of Norway, how awesome is that? Imagine a Disney-fied version of the story full of viking adventure, ferocious polar bears, and an encounter with an evil troll deep in Norwegian wood. The finale? A viking wedding of course.
The addition of Frozen Ever After may bring characters into a once character-free attraction roster, but remember, Donald and the Three Caballeros did that first. In my earnest opinion, think of this attraction as an experimental prototype dark ride of tomorrow. From this point on, we're only going to see dark rides of this caliber. Think about it. They'd be shooting themselves in the foot if they spat out a modern dark ride that utilized cutouts and animatronics with the mobility of a Macy's window display figure. Frozen Ever After has set a standard in modern theme park dark rides, and from here on out, it's just going to get better and better. WDI has done an excellent job of establishing the film's universe as apart of Norway in this attraction and I can't wait to see what the future holds for the rest of World Showcase. Would it work better in Fantasyland? Probably, but until then, I'll raise a glass to Anna and Elsa.
I appreciate hearing your perspective MEW, and in a lot of ways I think it is likely exactly how I'll feel on my next visit to Epcot (hopefully sooner rather than later). Having yet to experience the ride but having watched a few videos of it, it's very hard for me to just flat out hate it. Imagineering did the absolute best ride possible given the space and constraints they were given, and it shows. Although I don't believe every dark ride from this point forward will be of the same caliber, it's clear Frozen Ever After is a dark ride for the 21st century.
With that said, I'm still having a hard time reconciling with the fact that it is in Epcot, not so much because of what it replaced, but because of what I worry it means for the future of themed design in Disney parks. Today's corporate Disney sees the parks as nothing more than billboards for recent movies. The folks in charge have absolutely no idea what made Disney theme parks so special, nor do they care. They don't understand the fact that themed design is just a beautiful and important an art form as opera and ballet, and they're willing to shoehorn any property into any space so long as it will sell merchandise and get kids to watch Disney Channel.
I would point out too, that I'm not entirely opposed to putting characters into Epcot. I think it's a little lazy; when you take a pavilion designed to function as a futuristic underwater research facility, paste a couple of clown fish and a turtle to the front of it and call it an all new and improved experience, you're pulling my leg. But hey, if Nemo can educate children about the importance of clean oceans, then cool, I'm all for it. I just think there's a more tasteful way to achieve characterization and not dilute a park's theme.
A final note: You had mentioned that Maelstrom was one of Epcot's best; the truth is it wasn't, in fact if you think about it, Maelstrom was just as strange and just as random as DCA's Superstar Limo. From a viking village, to a polar bear attack, to magical troll infested woods, to a modern day oil rig, the ride had no sense of time, place, or story, and was really nothing more than a bunch of "Norway highlights." I contend the reason it's remembered so fondly is not because it was great, but because it, along with Living with the Land and (to a somewhat lesser extent) Universe of Energy, were the last 3 attractions at Epcot that still felt like EPCOT Center. These rides are not only full of old-school charm, they actually hold true to the mission and theme of the park, and remind people who were lucky enough to visit EPCOT Center in its heyday of the wonder and amazement they experienced.