What I find useful is to expand as fast as possible. Start by sending out scouts, you only need a few at first so you can map the system. Then start expanding as fast as you can. When you hit a junction point where two or more jump points meet hold it and build as many defenses as possible. And then make choke points between you and the computer. Find the routes that the computers will take to you so you know what plants to do heavy defenses on. The defenses will no hold back the computer but it should hold them off long enough for your main fleet to get there and beat them back.

Also go for the computers capital ships first. I have won many battles where the computer had three or four times as many ships as me by focusing the fire on the capital ships. Normally this will make the computer run away. Though this does not always happen now with the 1.05 patch. Don't sacrifice your capital ships if you can help it. if your capital ships are taking a beating retreat and regroup also build a ton of repair ships these things can really turn a battle. I have lost battles because the computer has so many repair ships that I couldn't kill anything.

Thanks for the advice guys. Will give it another whirl!

On huge multi random maps you will start on the edge of one of the systems and have one AI on each side, pirates on the center. After you explore around your homeworld, explore your sides to see who are they. Decide then which one you are going to take out and which one you're going to befriend. You'll probably want the one that gives you a "gimme X" mission. Or even better, a mission against the faction on your other side. With 50% standing or maybe less you can sign a Cease Fire and that's usually enough to switch your full attention to your target enemy.

I've had good luck thus far where I get my friend giving me missions against the faction I'm already fighting so I get to 100% standing with them and I can sign a Peace Treaty. I dunno if that's a nice coincidence or it's the way it's supposed to be.

Oh, and against the AI, preferably abstain on going with overkill fleets. By the 2nd fleet expansion you should be creating a small fleet in your center world, led by the 2nd Cap. Use this one to defend and expand on the gaps that your main fleet is leaving.