I think larger maps with more clustered nodes might be kinda nice. It would give more territorial feel to the game. With the current balanced layouts, particularly the 5 node one, it really does kinda force you to rush the middle comm node. Now, give me a cluster of nodes in the south east, with the AI having a group in the north west, with a good bit of distance between them, and I would have a lot more reason to leave forces back to protect it, or keep deploy points set aside so I can release a second wave if my base area gets threatened.
Even unbalanced, node distributions would make things interesting. Leading to a sort of uphill fight, against the equivalent of an enemy with the high ground. Maybe make this sort of thing favor the defender which would make steam rolling the AI later in the game a little more difficult.
Hazards other than nebulae would be nice too. Black holes, active stars, very dense asteroid fields that would be dangerous for capital ships and cruisers, whatever. They'd make the combat fields a lot less flat, and create things choke points.
Chapter 11 of The Art of War talks about various type of battlefields and how they require different strategies. Maybe look something like that, and figure out analogues for space combat.
Another idea would be to let the AI have a flagship with appropriate buffs. Take it out, kill the fleet commander, and you get some tactical advantage(pretty easy to implement with a fleet wide hit to effective crew level). Fail to take it out and the AI gets to keep a big mean ship that can control a lot of space and do a lot of damage.