I'm also quite new. Been playing less than two weeks.
Out of three games, I've won one. The others I gave up on simply based on the pressure from the AI's which felt too great compared to my situation.
The game I won was against two Difficulty 6 AI's, small galaxy (didn't understand what difference the galaxy size makes at first, so I started with small ones like 25 planets), probably 30 planets or so. AI's were Random Easier, the other was Turtle and the other Entrenched Homeworlder. I seriously wouldn't have won the game if it wasn't for two Armored Warheads that I used to bait the guards on the AI home world away from the Command Station. xD I had let the ship count grow way too big on that planet since I had unknowingly alerted it in mid-game, looking at near 5000 ships (some sort of cap, I think.), it was fun to see around 3000 AI ships and 23 starships go after two near-indestructible warheads and keep shooting at them even when their command station was under attack behind their backs, LOL. Felt like I cheated that one, but it was fun. Turned my game into a slideshow with so many ships too. At least now I know what I shouldn't let happen next time. ^^;
Been playing with Simple ship types for now. Next game I'll go Normal or Complex for sure, as I think I've learned the functions and uses of the simple types.
Anyways, my suggestion for a first game, if there's at least some RTS experience, and based on my first game experiences, would be Difficulty 5 or 6 AI's, 'easier' AI type for each, simple ship types, 40-60 planet galaxy, AI progress 1/30, no minor factions. There's plenty to learn there already.
Oh, and read the wikipedia pages and some forum posts here. I think I found tons of information here and there that is not mentioned in the tutorials or anywhere in the game. Mainly stuff about AI behaviour, priorities, stuff like that.