I've always heard that we should love G-d with all our hearts but also fear Him. I've understood all my life that fearing G-d is a fundamental midah, something every Jew must have. But I've also heard things and teachings that seem to contradict this:
The first example is a story (possibly a Midrash) of the giving of the Torah to Am Israel. This story says that before G-d gave us the Torah, he placed Har Sinai above all the Yehudim and said that if they didn't accept the Torah He would crush the mountain on them. Instead of answering that they would accept the Torah with fear, they answered with love and joy. Passing G-d's test. This suggests that G-d prefers we do the things He asks because we love Him, and not because we fear Him or the punishment.
The second example is Teshuvah. I heard from my rabbi that there are two ways of doing Teshuvah: one is because of fear of G-d and the other because of love of G-d. A Teshuvah made out of fear is accepted but it's not as good as a Teshuvah made out of love of G-d. This would suggest that doing things out of love of G-d is superior than doing things out of fear of G-d.
Should we actually fear G-d?