It seems like you are doing a good job of thinking through the options. It is generally a good idea to take the path of importing the companies first and then linking Contacts to the Company. This will provide a good foundation for later system expansion.
You can make the connection between Contacts and Accounts or Companies fairly easily by running an Advanced Find on all Active Accounts once you import them. Select the Dynamic Worksheet option as the Export method and then use the Unhide feature in Excel to reveal the AccountId or Guid for use with importing the Contacts. Associate this ID with the appropriate Contacts in your import file and the Contacts will associate to the Account or Company when you Import them.
You can also take the path of adding a text field to the Contact to store the Company but I would take the extra effort now to build the associate between the Account and Contact record as there are several advantages like Reports, Workflows, Campaigns, upgrades, etc.
With regard to the address, put the primary address for mailing purposes directly on the Contact record. By default, this will be the addressed used during a mail merge process.
Best of Luck with your implementation.
