"We made this decision based on what everyone needs."
I agree. Here's an example from the web: 我们可以根据大家的需要进行调整。(http://lib.utsz.edu.cn/article/view/id-252.html?locale=zh_CN) To my ear, your version is a more natural translation of the given English sentence.
根据 should always come in the front of a sentence. I can't really explain why, it's more like an inherent rule. Just like in English "Who are you?" is correct but "You are who?" isn't, plus it just sounds wrong. Like KX3 already said, you may hear it in a conversion sometimes, but usually as an afterthought. In a written text you will always see 根据 in the front.