Sorting with Voting API
Never mind I think I finally found the solution:

In addition to the settings above, I added a second relationships: Content: Vote results. It's the same relationship as before but instead of "Average vote" in the Aggregate function, I have "Number of votes." So as to avoid confusion, I also changed the identifier to: "Vote results (rank in group)"

So, I have two relationships, almost identical except for the Aggregate functions.

Then, in addition to the sort criteria described above, I added the same criteria again except that I chose the second relationship ("Vote results (rank in group)") instead. Order is also descending.

And that gave me the desired results: Nodes are properly ranked within the groups.

You can test this by enabling  Text to display under the stars: Both user's and average vote in the rating field.

:)

Hope that helps.