Or you might have been confused by the mission text as I often was.  On most campaign missions, you start out as a team with one or more races already.  Because of this, it's impossible to make an alliance with those races - the game considers a team to be superior to an alliance.  I remember being confused by this for quite a while my first times through.

Clan Lindsey's advice also works, too.

Other things to try to gain  an alliance:

• Establish trade routes with the other civilization.
• Offer them a research or economic treaty.
• Give them money or ships whenever they ask for it.
• Try to keep your borders from overlapping.

All those things will help bring your relations to 'Close', one step up from friendly.  They won't be willing to ally with you until you've reached 'Close'.  On the foreign tab, you can look at each races Report Screen - this will give you a clue on what you need to do.  I believe for Dark Avatar, the rule of thumb is to have 6 pluses.  If you have, say, 6 pluses and 2 negatives, you'll have to add 2 more pluses or erase the negatives or one of each.

That's more than I intended to type out, but oh well.  Good luck and have fun!

They're more open to negotiations when they don't have a military, so long as you don't have surrenders turned on (as they tend to surrender when they have no military), largely but not entirely because their militaristic opinion of you is determined by the ratio of their military to yours.  Wipe theirs out, and yours suddenly looks a lot stronger to them.

We may be speaking in different terms of "vastly superior" as well-if memory serves the two breakpoints are at 3x their military rating and at 10x their military rating, which is somewhat difficult for most players to achieve, and the latter even more so.