And does it matter where the envoys go and how many there are? Do i have to spread them out or what?
Yes. You can get no more than a +2 relationship bonus for a single planet. Multiple envoys will let you get to that limit faster, but once it hits 2 having more than 1 envoy is useless. You almost always send your envoys to different planets from the start. With one envoy at a different planet, 4 of them should give you +8 relations eventually.