I like the Alliance Victory, but found them hard to achieve (playing DL, large maps, tough). Now that 'tough' is getting easier for me, I noticed a couple of things.

First, a (very) high military score (say 300) really makes a positive difference in their attitude towards you. For a couple of games I tried looking at the plusses and minusses in the faction report to improve areas where their attitude was negative towards me. This didn't work very well. Now I'm just being an overall 'nice guy', leading to positive attitudes regarding trade, historic friendship and so on. I combine this approach with an uber military score and suddenly the majority of the races, regardless border proximity or ethics want to be my allies.

The second thing I have found is that this only works for a true 'nice guy' approach. In my last game I had a couple of alliances and some on close so I could end the game, but was continuing to do some experiments. I had this shiny uberfleet and I thought it was just a shame that I never use it. So I sent it over to the Thalans. The Thalans were soon crushed and their planets ruined (I abandoned the colonies to prevent an influence victory). However, the result of this was that the other factions didn't like me so much anymore and I could not get their attitudes to previous levels (can I get the 'historic friendship' back?). I can't get them any closer than friendly.

So it seems that alliances can be hard to achieve if you've been through a (couple) of war(s) and faction relationships get temporarily messed up.