Learn Russian: Была страшная погода.

Yes, its literal meaning is "scary" or "frightening" (from the noun страх, meaning "fear"). However, Russians frequently use страшный to mean "terrible," "awful," or "severe." It's very similar to how English speakers might say the weather is "frightful."

Why does the verb Была come at the very beginning of the sentence?

In Russian, putting the verb first to set the scene is a very natural storytelling device. While you could say Погода была страшная, starting with Была acts a bit like saying "There was..." in English, introducing the situation right away.

Could I use ужасная instead of страшная here?

Absolutely. Ужасная погода is another extremely common way to say "terrible weather." In this context, ужасная and страшная are practically synonyms, both describing severe or awful weather.

As a quick refresher, why is the verb была feminine here, rather than the neuter было?

The verb must agree with the subject in the past tense. Because погода (weather) is a feminine noun, the verb takes the feminine ending, becoming была. Learners often confuse this with impersonal descriptions of weather, like Было холодно (It was cold), which do use the neuter было because there is no physical subject noun.