Does it take an extremely long time to get to this level?
Yes usually. Giving free gifts helps (even cheap stuff like "missile defence theory"), but you have to wait "a couple of months" until you can speak to them again.
Trading helps. Even when the relations displays the max "++" ("trading++"), sending more freighters to them still improves relations. Some races like trading more than others.
In some games, I choose my ethical alignment to match races I want to be friendly with.
"our military strength" seems to carry a heavy weight, especially with evil races.
Give them an economic treaty in return for a load of techs. You get "our treaties together++" and they will be unpopular with other races if they start a war with you, but so will you be if you start a war with them.
