I've put $company as part of the Address Format and now it shows twice! One time at the start of the Address and also where I want it in the actual address. What the heck?

This is due to historical coding going back many years, prior to Phoenix. You simply need to override the cd_traditional_address module (and its language file), then amend function format( to better suit your needs. In this case, simply comment out these three lines as shown;
If you comment these lines out, the COMPANY will show only where you want it - you must therefore ensure that you add $company to ALL of your Address Formats.