It works instantly here with 74b2/W10. Have you enabled access to the OS X address book, both in TB (under File) and OS X (Privacy), or is this with just local (not directory) TB address books?

Fair points. I am using only "Local Address Books" (no "Directory Server"). On top of this, TB has access to the Contacts -the only thing it has requested access to-.

And to clarify: it works, but not properly. While before I would get results by simply typing a letter or two, now I may even type out the entire first name without getting a single suggestion. Once I get the suggestions (as described above) they are correct. But they take many characters to appear, which makes it impractical.

If you disable access to the OS X Address Book in TB, does it make any difference? If it doesn't, try creating a new address book in Address Book, add a few test contacts, and see if autocomplete finds those contacts correctly. If it does, it may indicate there's something corrupted with your other address books.

I am convinced I do a terrible job explaining, so I will go with pictures :D

In this example, I made a new contact (zzTestFirst TestLast). It only pops up after the third letter is pressed, although there are only six matches containing "zz" in my contacts.

Is this new contact in a new address book? You've already shown that the current address book doesn't autocomplete. Did you disable the OS X address book? That makes the setup the same as on Windows, which I find works. Before reporting this as a bug, the testing has to be systematic so that a developer has STR (steps to reproduce).

When you say disable the OSX Address Book, what exactly do you mean? Restrict access from TB to the address book from the Safety and Security? Because this, indeed, works, although both the test name (zzTest) and 99% of my contacts are in the "Collected Addresses".

Renabling it, causes the same erratic behavior, even if I try to find a newly created contact in a newly created address book. Weird.

Since I do not need any of my OSX contacts, for me this is solved, but it seems there is something there. If you need me to try something out, I am more than willing to do so.

By disable, I mean to simply uncheck the setting under File so that TB no longer reads from or searches the OS X address book, leaving just Personal Address Book, Collected Addresses and any other address books in TB as the only ones searched by the autocomplete function.

I haven't seen any reports of this happening with the release version, 68, so it appears you've found a bug in 74beta: address autocomplete performance degraded when access to OS X Contacts enabled.

This has been submitted as a bug: https://bugzilla.mozilla.org/show_bug.cgi?id=1615468

The workaround is described above: disable access to the OS X contacts.

This should be fixed in 75b1, now available.