Yeah, I always tell new players in my circles that are just trying AI War for the first time to go with no minor factions or AI plots the first time around, and to put their faith in their abilities as strategy gamers in a safe little box to take out later after they've tried the game at lower difficulty.
I will never forget how the AI blasted me through the pants on my first attempt at a campaign. I'm pretty sure this was on 7 since I always go into games on the "normal" difficulty. So yeah, 4 or 5 is where I tell new players to usually start, just so they can play the game for a bit and get a feel for actually managing the game and its basic concepts before diving into the bag of nasty tricks where all the fun lies.