Are there mail clients that actually support things like priority inbox and categorization that don't simply crumble for large inboxes?
Of the exemplars listed, nmh is by far the most flexible and capable of handling large inboxes. The reason why is that it is a set of command-line executables which can be scripted with whatever language you prefer. So prioritization and/or categorization is a matter of how one wants each to be defined.
I used IMAP via fetchmail[0] with nmh to allow multiple MUAs (on different machines and/or OSs) access/management to the same email accounts with great success. IIRC, for nmh I used lynx to render HTML messages and xview to display image attachments. Other attachments were processed separately but had similar workflows.
I have not used mutt myself, but have heard great things about it and it is definitely worthy of consideration.
I want a client that is simple but flexible by default, extensible, themeable would be nice, and for the love of god has key shortcuts for everything THAT CAN BE CHANGED. LOOKING AT YOU, THUNDERBIRD.
Thunderbird is almost usable for me, but the UI is just absolutely abysmal. The kicker is not being able to change key shortcuts, making Thunderbird unusable for me.
This is where email MUAs[0] shine. Mail user agents such as Thunderbird[1], KMail[2], Apple Mail[3], and nmh[4] (for hard-core Unix command-line aficionados) support filtering and automatic categorization to varying degrees.
All while being mail service agnostic.
0 - https://en.wikipedia.org/wiki/Email_client
1 - https://en.wikipedia.org/wiki/Mozilla_Thunderbird
2 - https://apps.kde.org/kmail2/
3 - https://support.apple.com/mail
4 - https://www.nongnu.org/nmh/