Its also true that the AI won't ally with you if it doesn't see you as being able to help/support it. If your military is too weak, the AI will see it as you mooching off their power, not you standing as equals.

They can be stronger than you, but if your military is ranked lower than 4th or so, you won't get that alliance.

Well, military is an important factor but not the only one.
Check the "Report" on the AI civilizations and look at plusses and minuses.
Each plus can be improved to 2 plusses; some minuses can be negated as well. That should give you a clue how to get to a close relationship.

And of course overwhelming military score helps an enormous lot (hint: Spin Control Center )

Difficulty factor makes a difference as well, or at least I've had that impression multiple times.
Improve your diplomacy, if necessary research "good or evil" to choose the same alignment as most of the AI's you want to ally with.
Research all trade techs and send the maximum number of freighters to the AI's you want to ally with.

Most of the times this works fine for me without having to send them any gifts.

Maybe my answer is off-topic but;

To me, Ethics is a pivotal point during any games. It defines how & why you may win or lose. All of the essential activities will suddenly fall in place like dominoes. 85% of the results (war, trade, ecomony, etc) are directly affected by THAT single choice.

Lately, i've taken the toughest route. I purposely go against the tide -- and, it IS a real blast.

4 Neutrals, 5 Evils --- didn't care; i happily clicked the GOOD side of the force and i got served a wild ride. Red tags were tumbling like crazy to the right and by George, it didn't matter much until yours truly declared a galaxy wide reorganization of still active opponents.
Allied or not, btw.

If your military was pehaps stronger they would give you a few bc to form an allince. Or if you had a few more pluses in the relationship.

The close relations just allows the option to present itself on the trade screen. That doesnt mean the AI will automatically accept it without something on the side.