Honestly, I would prefer Oblivion style. I didn't like Morrowind's tutorial too much... because I didn't really know what on earth I was choosing. I had no chance to try different skills. It's something I understand, because I can't see a way to let you try your different skills when you are arriving to the census and all of that... Anyway, I liked how Oblivion did it, showing you what was going on and showing you your different options.
Well, with not class system in Skyrim you don't have to know what you are choosing and you can try different skills to your hearts content. If you don't like using a particular skill as it doesn't fit your playstyle you can change it freely. The class system in MW and OB allowed you to do the same, but with picking major/minor skills some, like myself, when we didn't like what we chose would make new characters instead of keeping skills that didn't fit how we played. With Skyrim you won't have that problem.
Now for the "introducing us to the story" I can do without it in Skyrim as it seems that from what Todd said, early in the game you will learn what's going on with getting your dragon shouts etc...