I know that much of the initial scoring is based on the traits (Xenophobes don't like anyone, certain traits rub other traits the wrong way), but what actions can I take to positively influence potential allies?
Many of the options available to me are mood killers, and are great for cajoling them into being hostile enough for open warfare (including just existing near their borders). By comparison I just don't seem to have the have the tools to push an empire those last few points towards accepting an alliance; I can only make so many lopsided trade agreements before it bleeds my coffers dry (and I'm not sure multiple such trades have much effect), and I have a limited number of embassies to spread around.
(This is not the empire that's only a few points away; that empire got snatched up by another alliance, and their 'acceptance rating' now has a -1000 attached to it.)