If Steve is that Steve and creator of awesome Aurora 4X then he know well when complexity of UI is becoming a huge problem.
I can't suggest anything reasonable about tutorial - my last played tutorial was in WC3. And I lost human campaign first mission Yean, it was so good to be young :(
But I will suggest to not overdoing on it, especially when game goes Steam. Even in casual games here most of players never complete game on default difficulty. And poorly designed tutorial will do more harm then help (Factorio story - they'd forced to redesign in finally), while good tutorial may require too much coding & design efforts from a single dev.
Let's be honest - game UI is atrocity for average player of GTA5 era and it's impossible to change it. Hell, even Stellaris is too complex for many, many players despite all Paradox's efforts. Screenshots of game interface will clearly warn everybody that game is ... wargame-like. So most of buyers will be quite hardcore players.
P.S. IMHO another option is to make a good game encyclopedia, something like Paradox's have for their own games. Sure, it's less pretty then good and complex tutorial system, but may require less work for Vic plus some of us may help a little with content for it. Dunno, maybe it's my personal quirks but I'm fine to play game keeping it's wiki open & used a lot.
I wish! Aurora is amazing, but I'm actually developing another game with a similar complexity curve to SE. And what testers are telling us loud and clear is they need more direction. We're probably going to do a multi-chapter in-game tutorial, but as I said at the beginning I know it's hard to make a good tutorial. It's especially hard when you're making changes literally after the game is published, but I think people understand at this point that games are living entities and they can and do change over time.
I think you already have the backbone in place for a decent guided tutorial - you already have an advisor giving hints - just chain those together into a small scenario with a RC-like start and I think combined with an expanded Help tab (what's there is good, there's just not a lot of it) and focus on each major axis of the game (exploration, warfare, diplomacy, science, councils, and leader care and feeding) and I think it would go a long way towards easing the curve for most people!
Lifetime "You Magnificent Bastard!" callouts: 5
Lifetime slaps across the face by a female: 2
Lifetime games that hold my attention longer than a month: 3