After having restored the altar at the temple of Halcyon in Vooriden, I try to turn in the olive branch to get the blessing. I keep getting a message saying that I am making the correct offering but that Halcyon refuses it for some reason. I already have the blessings from Ter'el, Makaal, Alberich, and Geshtianna.

One thing, the blessing from Geshtianna was from the priest, not the altar itself (the one you get for bringing back the altar.) I had assumed that was going to work but maybe not.

I am finding out that for supposedly having "an entirely non-linear storyline with surprising plot twists" that this game definitely requires you to follow everything in a line and by jumping ahead I have already broken the quests a few times.

Please, if anyone has any idea what the problem is, please let me know. Feel free to throw in spoilers all you want.

Mae

You need to make an offering at Geshtianna's altar as well, priestess' blessing is just a reward for completed quest.

What Thiev said.

There are definite lines you have to follow, most of the plot lines though have multiple options and things to do within the particular macro plot. Yes, it is linear to a degree (more so than, say, the Elder Scrolls games) but it also provides options within the linear nature of quests.

Also, the way you broke the plot (the gods' blessings) you aren't supposed to be really know about until you run into each altar. There isn't a place in the game that lists where each altar is, you have to search for them (or find a walkthrough online). Of course that is possible, and it is possible to break the plot because you know what you are looking for and where, but in a "clean" run through of the game you are supposed to have no knowledge of the altars being places and so on. I'm not judging you for choosing to do the gods' quest (and looking up how to do it, since it is difficult to figure out in game) I'm just saying that the way you broke the plot makes sense since you aren't supposed to know where you have to go until you are told to go there.

I've encountered the same problem as above.

I'm not quite clear what exactly has gone wrong. Did I break it; And if so, how? I did go to Stillwater a little prematurely - Is that why? I had no clue that there's some kind of huge, over-arching blessings of the god sorta Quest to which the blessings from the altars are tied.

It's true, getting all the gods to like you is not unlike trying to defuse a bomb. Blessing will be secured and lost, alliances must be forged then gently broken, and always there is an order to them.
It's a pity your first encounters with the altars is before your first encounter with the men who have spent time trying to solve their puzzle.