Starting Strategy

You seem to be doing the right things. Just do it more efficiently, faster I mean (if you can defeat Hard AI without relying hard on a starbase I guess you are fast enough). AND place a starbase under your opponent's nose, with a small fleet you can defend until you build a titan. Until the base is built staying alive is a hard task, but after that it's piece of cake, just don't lose the starbase and you are fine. There was a time when a Transcencia and a lone Progenitor could save my ass from several waves of TEC assaults.

If you want to be faster than the AI, I recommend skipping some planets. Scout the map, select a planet you think you can defend, colonize some asteroids near your homeworld for the extra resources, and build a starbase constructor as fast as manageable. Then send your fleet to the designated chokepoint, no matter how many planets are left uncolonized on the way, colonize it, build the starbase, and you are fine against Unfair AI. After this colonize left planets, basically do what you want. A small escort fleet and a starbase supported by repair platforms wins you the game. The AI has no idea how to kill that base without losing ships worth 1000-2000 fleet supply.

I always build trade after I fortified that chokepoint, I tend to rely on the raw income i gan from expanding fast, rather than forcing my weak economy to pay for trade ports and logistic slots.

Remember that the Unfair AI and above have very fat cheats to them; I think they get something like triple resources from their planets, which means they are going to flood you with units, superior in tier, number and upgrades.

The only things you can do against unfair AI are, to my knowledge:
- do something that will perfectly hardcounter their composition (early game, AIs like to spam LFs. If you quickly get LRFs and a lot of them, you will have a temporary advantage; if you use it right, you might score something)
- abuse their relatively slow expansion rate. AIs dont expand too fast, you can easily have double their planet numbers in the early game. If you focus on Planets that don't need a research, numerous civ upgrades and have a lot of asteroids, you can get a temporary lead in resources.
- starbases. AIs suck against starbases. For some reason, the AI will always think they can break your starbase with a force that's about 3 or more times too small for the task, which makes starbases very potent against AI, as chokepoint blockers or for rushes. Of course, this won't last forever; Unfair AI has a tendency to "learn" over time, albeit very slowly. If you leave your starbase without much attention, the AI will send wave after wave of ships... the first ten will be dumb, LF+LRF+HC fleets that die instantaneously. Then, you will see some poorly managed carriers. Then, you will start seeing anti-structure cruisers. Finally, after 15 or so waves crashed on your starbase, you will see the AI bring 40 Ogrovs to your gravwell... as Vasari, it's hard to deal with; As Advent, probably not. As TEC... not sure. But it's a surprise that may come if you rely on that SB too much.
- use some other broken tactic the AI sucks at countering. I'm pretty sure some of the guys on the forums know at least 101 ways of screwing the highest AI level within 10 minutes.

Just so you know, if you save a game and reload it you can change the AI difficulty after the fact.  That way, if you want, you can try using a lower-level AI until the early-game period is over then bump them up to unfair.

One thing that's easy to do is to put off upgrading your fleet supply initially; don't.  Getting the extra set of reinforcements is helpful economically since you'll be able to expand faster (barring the possibility that you run short on credits due to excessive planetary development and possibly underdevelopment penalties), and its critical to get the first fleet supply somewhat early as otherwise you'll be pretty vulnerable to AI rushes.

As the starbase strategy suggests, the AI are pretty easy to lure into deathtraps.  Getting 1 or 2 capital ships leveled in early game is pretty important, especially if you can get an early level-6 Marza as the TEC (although that means you'd have to sacrifice either an early Akkan or Dunov, since you don't want too many capital ships early on).  The fewer capital ships you have the better, as you get reduced experience for having multiple in the same gravity well (and leveled capital ships are vastly superior to stock ones).

The AI are idiots when it comes to repair yards; you can keep a fleet alive far longer than is at-all fair by having several of them close together, which is critical with starbases but also very helpful if capital ships are holding a chokepoint.  Turrets and mines are not particularly cost-effective by comparison, although Vasari turrets with the disruptive nanites are a pretty good counter to large ships as they disable all passive regeneration.  Otherwise, you'll want primarily light carriers and as early a titan as possible.  Light carriers are typically able to counter effectively anything well, since bombers are immune to most weapons and the AI is too dumb to actively seek out carriers if you have something else distracting them.

If you play the Vasari, the Kortul Devastator is an incredibly useful capital ship as your second; it will level up surge quickly, making it effectively invulnerable to anything but absolute overwhelming force.  Given the AI's capacity to ignore repair yards and distant light carriers, this is an incredibly valuable attribute.

You should be able to expand in 2 directions without any fleet supply upgrades...if you are going against unfair, you aren't going to match them in fleet size anyway, so why bother?  Better off saving your money for SB constructors and eventually a titan...

Unless you are Vasari...you may want one fleet upgrade to support your Orky rushes, usually with either corvettes, carriers, or overseers (and of course a minelayer)...

I have to agree with Sel. I tend to hold off on the first upgrade so I can get a good economy going. When I do get a fleet supply upgrade I make sure I can fill it immediately otherwise it's wasted space.