I have conflicting thoughts about Cornelius (Acts 10). It says he feared God and was always praying to Him. If he feared God, how could Cornelius trust in God?
I think you may be using the wrong definition for fear. Fearing God has always been a requirement for men to follow God. Abraham is said to have feared God in Genesis 22:12. Many other people are praised for fearing God (midwives in Exodus 1:21, trustworthy men in Exodus 18:21, Nehemiah in Nehemiah 7:2). It is also commanded in the Old Testament in many places like Deuteronomy 6:24. Maintaining a fear of God is a part of how to keep from sinning (see Exodus 20:20; Leviticus 19:14; 25:17,43 and many others). In fact, evil men are described as those who don't fear God (Genesis 20:11; Luke 18:2).
The fear that is being described by these passages is the healthy respect for who God is and what He requires of man. There are a lot of people who think they know better than God. When the Bible says to do something, they not only don't bother to do it, and they will complain if someone tells them that they need to do it. These people are showing by their conduct that they have no respect for God. They believe that God is a being who can be manipulated or coerced into doing what they want to do.
Take for example a passage like Hebrews 10:31, "It is a dreadful thing to fall into the hands of the living God." Why would anyone write a verse like that? Why did the writer of Hebrews not say, "It is a good thing to fall into the hands of the loving God?" It is a dreadful thing because being in sin is a dreadful condition. If one goes through their entire life and refuses to acknowledge God's sovereignty, they have no hope of being saved. As it says in Hebrews 10:26-27, "If we deliberately keep on sinning after we have received the knowledge of the truth, no sacrifice for sins is left, but only a fearful expectation of judgment and of raging fire that will consume the enemies of God." And that is what it says about Christians who stop doing all that they are supposed to do.
There is a reason to be motivated by the fear of God. Because God is all powerful, He can and will send people to Hell (Revelation 20:15). That should motivate us to get on His good side, if it were at all possible. If it were possible to earn such a spot, we would all be trying real hard to earn it. However, we have all done enough wrong that earning salvation is not possible. Our only option is if God extends grace. He offers grace to all, but only promises to grant it to those who meet His conditions of humility (James 4:6) and obedience (I Peter 1:2).
What we have in Cornelius is a man who was not under the law of Moses, but realized that the God of Israel was the true God. He therefore behaved like someone who believed. Just because he was excluded from being a Jew, does not mean that he could not acknowledge God. God was known to deal with believers who were not Jews in the Old Testament. In fact, the story of Jonah is one about Jonah hating the idea of having to preach to non-Jews. God showed Jonah that he cared about all mankind and, therefore, made a way for the men and women of Damascus to be pleasing to him. Cornelius must have known that about God and, therefore, he trusted God.