The drop down list will revert to that pop up Record Picker when the list of choices gets over 1000.
An idea to retain the regular drop down is to set it up as a conditional drop down where the user first enters the first letter of the choice into a new field and then the actual choice would be displays, and would then just list, for example all the choices beginning with the letter A.
As for automatically linking up to the Parent, the contacts import would need to populate the field typically called Related Company. If the key field to the Company table is [Record ID#], then you would need to export the company table with the company name and the [Record ID#], use VLOOKUP in Excel to get the Record ID into the contacts and then import that field into Related Company.
Alternatively you might make the Key field of the company table to be the company name. If you have never changed a key field, i suggest trying it in a copy of your app first. Then the imported Contacts would link up automatically if the Company name was a letter perfect match.