For conversational Korean between adults in informal situations, I would agree with HK Lee that the most useful style to become comfortable with is the haseo / haeyo style. This can be called 해요체 ('Haeyoche'), and is considered a polite but informal style. I guess that means my answer is 'no' - it's not necessarily better to learn a formal style first.
One thing that is definitely worth understanding early on is the use of the (으)시 / (u)shi honorific particle in verbs. In my experience, this is the most important mechanism for showing the necessary politeness to the person you are talking to or about, which is often more important than formality. A related issue is using special polite forms of some verbs and nouns, such as 'tushida'(드시다) instead of 'mokda'(먹다) for eat.
Having said that, being comfortable with switching the endings on verbs to speak in (and listen to) different levels is an important part of the language, so I would hope any good Korean course wouldn't let you go too far without introducing you to different levels - so if you find a good course that happens to start of teaching a formal style, I wouldn't see that as a big negative point.
I was wondering if this would appear odd to Korean speakers if I talk solely in a formal fashion?
It probably will, if you're not in a formal situation - but that doesn't really matter. There will be plenty of other odd things about the way you're speaking, as a beginner!
By the way, you will quite often hear common phrases like 'hello' - 안녕하십니까 (annyeong hashimnikka) or 'thanks' - 감사합니다 (kamsahamnida) spoken in formal language, even in situations that aren't really that formal. In these situations, it is common for the rest of the conversation to carry on using less formal language - so just because you hear 'kamsahamnida' a lot, don't be fooled into thinking people are being formal with each other most of the time.