A tutorial can be phrased as an internal dialog of the sovereign, if you're worried about breaking immersion.  I'm fairly confident that there are some fun conceits to play with in that regard.

A tutorial also gives firmer control over the player's initial experience with the game, which can be helpful.

I would like a tutorial. 

Also, when faced with loading screens, a pool of one-line "tips and tricks" is pretty standard now-a-days and I think they're a good idea.

What if your advisor is a sort of familiar.  You can choose to have a wise owl for an advisor, or a defensive minded turtle etc...

If you're going to have a campaign, then the first, preferably optional, mission should double as a tutorial. Many people, myself sometimes included, will jump into a game without reading any of the manual. In the absence of a tutorial, it means you just have to figure things out yourself and it is usually pretty easy to go a long time ignorant of some very basic parts of the game (I could imagine people not really knowing how prestige connects to many game mechanics, etc).

Some tutorials fail because they try to do too much; a tutorial will never teach a new player to be an advanced player. Keep the tutorial simple, use it to familiarize players with the game's foundation and any concepts or mechanics that aren't self-explanatory. Essentially, a tutorial should give a good enough grasp of the game so that when something happens, they can understand/figure out why and how it happened. For example, there will be too many structures for a tutorial to cover exhaustively; instead the tutorial should be focused on providing the player with the insight necessary to understand what all the buildings do based on their infocard.

A civilopedia-type interface goes a long way, as well. Don't remember what that particular property does? Look it up in-game! It's like having an in-game wikipedia, where all the information a player could want is available. If I look up "Prestige" it should tell me exactly what it does, and what affects it.

I think the combination of a tutorial with a "civilopedia" is the best combination; the tutorial helps you get started, the civilopedia helps you learn the ins and outs of everything as you encounter them, at your own pace and also gives advanced players a place to go if they forget or want to double-check something.

Advisors are great for beginners, but tend to be very annoying for advanced players. That, of course, depends on their implementation. For example in SimCity 2000, advisors warnings were useful, but I usually ignored their advice and solved the problems in my own way. 

I also like to have a tutorial in the game. I think a well done tutorial is essential in making a game, especially a 4x game accessible to new players. Prologue in a campaign is an usual but perfectly acceptable way.

Advisors would be nice for intermidate players but i would also like it very much to see them represented in a meaningful manner in the game world - be it as a real circle of advisors you have to recruit with their own bonuses and personalities, different familiars or companions. It would get annoying to see the same 3 or 4 faces with the same advices playing kingdom or empire.

A good civilopedia which also should be easy to adapt to mods is a powerful tool for any player, beginner or advanced alike and should be included as well.

Last but not least i really would like to see a good printed or pdf manual, but this manual will get more and more inaccurate as the game gets updates, so the integrated game help is more important in my opinion.

Aye, a tutorial is nice to have. But an elementopedia is a must.

Imho it's much more useful for new players to be able to click on context sensitive links in game which explains them what certain buildings and concepts do then a one time tutorial.

For example, when I build my first city it currently says:

Because this land is forsaken, it will cost 5 your essence to build on. Acceptable?

This doesn't tell anything to a new player. (Btw. it also needs it's grammar fixed. ) A newbie doesn't know what forsaken land is and what's that essence stuff he's supposed to spend on.

Because this land is forsaken, it will cost 5 your essence to build on. Acceptable?

Forsaken leads to an article explaining native land types for Men and Fallen.

Essence leads to an article explaining the game concept behind essence and what's it used for.

This is much more useful for new players since they can ask for crucial help when they need it and it goes much better with the game flow.

If you look over the general forum there's a couple of "new tester, what do I do?" threads. For anybody who has already played a similar TBS game, it's fairly obvious how most of the controls work and what you're supposed to be doing (except for how to send units together as a group, THAT part of the UI needs work).

But for a player new to this type of game, exactly what they're supposed to be doing at the beginning of a game is pretty mysterious. Those people are the ones who need a tutorial, and that's even more true if there is eventual plans for a demo version of Elemental. When a new person is trying it, you don't want them to give up because they don't know how to build their first city.

Do you guys remember Civ2? It had advisors, six of them, if I remember correctly, each representing a facet of you empire. Sometimes the advisors weren't in touch with reality, but often they could give you a quick glimpse of what's wrong in their area. For example, to this day, I remember my military advisor saying 'You need to build more ships, your majesty, and LET THE SEAS GET RED, WITH BLOOD!'. It was voice acted, and was awesome.

As for Elemental:

Advisors are an excellent idea. Suppose, in mid-late game, you open your finance tab to see why you are losing money. Now, an experienced player could tell from the data what's wrong, but even he would need some time for that. An advising AI, on the other hand, could simply point the player's attention to the fact that, say, the army is just too big for your empire and you can't support it. A player who is unfamiliar with the mechanics won't be able to judge whether it's the army that is too big or whether it's his economy that's in shambles.

This may not apply exactly, but one of the features Worldwide Soccer Manager (aka Football Manager) implemented in the past few years was bolstering the advice of the assistant coaches.  The game had so many options and strategies that having AI help you make choices made the game so much more playable and informative.  Now, not all of the advice was good or accurate (it was your job as the manager to determine this), but the advice made the game so much more enjoyable.

Advisors coupled with charts, graphs, and data really would help to formulate a great strategy.  This is assuming they're helpful and provide good advice, but this probably also fits in with AI programming work anyway.

I vote for a tutorial for two reasons:

1.  You'll be docked by reviewers for not having one.

2.  It will help you better identify with players playing for the first time.  What things to they need to know?  How do they interact with the game?  This keeps your focus on usability.  It wouldn't have to be long or extensive but available for those that want it.

i vote for tutorial videos i always learn the most from them

I am all for a good manual (in fact I got the limited edition mainly for the promise of a big fat tome of a manual) but we must remember that a lot of people will be getting this digitally. In that format a pdf manual is only of limited utility as it is tough to refer to while playing the game and frankly not all that readable even in better situations. With that in mind some kind of in-game assistance is vital.

For a tutorial, I always liked the way the first Imperium Galactica was set up. The entire map was present in the game, but you only had access to small bit at first. As you progressed you would increase in rank and the scope of what you could do and your area of responsibility would increase.

It kept you from having everything thrown at you all at once.

Event tree, Nah make it a Tech, You could have Tutorial, Advanced Tutorials, and Refined Tutorials

Of course you only can research this tech if you have a Pioneer who have built a Tutorial improvement which is on the little island out in the sea gaurded by a dragon.