How do I add new contact and company records at the same time?

There are two ways that you're able add a Contact and a Company at the same time:

From the + Add menu, select Contact. Then, in the Company picker field, enter the name of the company. After that, select Create as a New Company to open up the Add Company screen.
On a saved company record, from the Actions drop-down, select Add Contact.
- S-Release: Click the Select an Action button on a company record to add a new contact.