Bane,
I do a lot of harmony writing for/with folks and there really isn’t a hard fast rule here either. First though, if the artist has some ideas, I start with them and go from there. Other than that, this is what I consider when I write harmonies:
The hooks of the song: do something special there. Use the intervals of the instruments, vocal and harmony to form something beautiful at that point. Foreshadow it in the verses of the songs.
I view harmonies like skipping stones. The stone being the harmony and the water being the body of the song. The skip comes near then go away, near and away, eventually sinking. The sinking point is what I consider the hook sections, usually at the end of a verse or chorus, where everything becomes one. Sometimes I focus on the hooks first then build the harmony backwards from there.
I tend to keep 1st verses empty or very sparse of harmony and usually introduce the harmony in the 1st chorus lightly. After that the gloves are off and I follow the song’s movement and have the harmony’s energy follow the movement of the song. I still hyper focus on the hooks of the song. This isn’t a hard rule. The song should dictate where the harmony should come in, but I usually fall into this type of approach because the harmony can be one of the things to make a song very memorable and you don’t want to give up too much at the beginning of the song.
Read the lyrics too. Understand the power of the artist’s words. Find the key areas of their lyrics and have the harmonies embellish them. If the song was well written, these should coincide with the hook areas.
This and this are prime examples of my considerations of harmony and how to use them to the advantage of the song. This work is a few years old. If you want some recent stuff, P.M. me and I will see about getting you some current work. Anyway, The latter link is a band that I now play in as the DB player moved to Maine. The music was what was done when they were a unit in my joint.
When in doubt or in a search, take a listen to chart busters that fit the genre of the music you are working on. Dissect their harmony work in order to understand and to apply to your own. Modeling is an exceptional way to wrap your head around something and to gather experience that will then provide you the ability to create your own. <–Read that last line again.
Good luck!
If totally lost, let cubase figure it out for you! 
(kidding kidding)