Backlog Refinement - Averaging to numbers that aren't in the Fibonacci sequence

What if you were using t-shirt sizing and 3 people vote for a Medium and 3 people vote for a Large.  Would you average that together and come up with a Medium Large? Or would it be a Large Medium?

The Fibonacci sequence (or the modified sequence used by some) is used for relative sizing and sizing is a guess based on the information you have at the time of doing the estimate. It doesn't need to be exact.  Relative estimation is an activity where you estimate one story in relation to others.  Let me paraphrase an example that Mike Cohn used in a class I took. 

Imagine you are standing on a street corner. You are trying to estimate the difference of walking between 2 buildings within your line of sight.  Both are within 200 feet of being the same distance from you.  Based on that you could say both are 3.  But you just noticed that there is some construction on the sidewalks between you and Building A.  That could cause you to estimate the walking from your current location to Building A as a 5 while the walk to Building B is a 3. There is a person standing beside you who will be walking with you.  They estimate that Building A is an 8 and Building B is a 5. Why?  Because she is injured and uses crutches to walk. Which one is right?  Who knows. But a conversation should occur based on the differing estimates and all parties involved can agree on a value to use.  They may end up agreeing on the value of 3 for Building B and 8 for Building A. 

There really is no use in averaging, just discuss. Have the individuals explain why they picked the estimate that they did. It could be that one of the people has some information that the others didn't and that information is the key to have everyone agree. As long as the team will agree to use a single number from the series you are ready to go.

When going through Scrum training and reviewing sources, I've understood that teams need to stick to the Fibonacci sequence when estimating stories in Backlog Refinement.

What training was this, exactly? Scrum does not dictate that teams use the Fibonacci sequence for estimating. Scrum doesn't mandate the use of any particular unit on estimations. In fact, you don't even need to assign a numerical value for an estimate - breaking down Product Backlog Items into roughly equal size units of work is sufficient.

The entire point of estimating Product Backlog Items is to give the Product Owner insight into making tradeoffs when ordering the Product Backlog and to help the Development Team determine what Product Backlog Items make sense in a Sprint. How you achieve these objectives is not specified by Scrum.

If a team is half and half on an estimate (example: 3 people vote for a "3" and 3 people vote for a "5"), should they need to pick a Fibonacci number and not average it to a "4" as it is not in the Fibonacci sequence?

Have you considered consensus-based estimation? Why did some of the team think that the Product Backlog Item was a "3" and others think that it was a "5"? Did the team have a discussion and make sure that everyone understands the work that is expected to be done when the Product Backlog Item is considered complete? If different people are reading the same work and coming to different conclusions, perhaps the definition of the work is unclear or people's understanding of what is required to complete the work is unclear, but the lack of clarity should be resolved.

should they need to pick a Fibonacci number and not average it to a "4" as it is not in the Fibonacci sequence?

Which is more important - the number a team arrives at during estimation, or their shared understanding of the work that will be involved?

As always, Ian, one question to take the complexity out of a discussion. Thanks.

In the event that they would really not agree on a common number, we would pick the higher one. 

Why?

To reduce risk and most probably the one who gave the higher number sees the requirement/feature on a different light. But this RARELY happens and this is something that should be considered as a norm.

This is an example. FE and BE devs both provided 2 but Testers provided 5 or even 8. They said that the change will require a lot of manual testing that could probably take them hours or even days. This happens because most dev team members only think on the task that thy're gonna do, and not the whole work that the team will require to perform.

That mentality is the one that you need to address.