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.