Sure,
On the table with the 1001+ choices for Company make a new field called [Company First Letter] with the formula of
Left([Company Name],1)
Then on the details table where you do your data entry make a new field called [Company First Letter] and let it just be a data entry free form text field ( you could also experiment with a drop down field with 26 choices A-Z plus 0-9. (I'm not actually sure if the Conditional drop down will be case sensitive, like if you have a company name entered with a lower case first letter).
But let's start simple as a free form field. Limit that to 1 character maximum length in field settings.
Then go to the field properties for Related Company and check the box for
Conditional values The values in this field depend on a selection in another field
and specify that after [Company First Letter] is selected only show choice where that is equal to the value in the field [Company First Letter]
The auto filtering of that drop down list is extremely fast but will only begin when you make a selection from a drop down list or you tab out of a free form field.
So I suggest to start with a free form field to choose the first letter and if you don't like the user experience, change it to a drop down field, ... but in typing this I suppose a drop down field is better as you can also just type a letter like Z into the drop down list and it will choose Z and then immediately filter the company list to your Zanzabar and Zebra customers.
If you have a customer named Zyzzyva it would be worth 43 points in scrabble and as I'm sure you aware, but for the benefit of others, is a genus of tropical American weevils often found in association with palms, and it's a snouted beetle (as opposed, I suppose, to a just regular old beetle).