Search is my biggest issue too. I switched out of gmail to my self-hosted server using roundcube and searching through IMAP is excruciatingly slow compared to gmail, even after I moved the mailboxes to an SSD.
I am not sure whether this is a limitation on the IMAP protocol, but I suspect a proper replacement to gmail might involve coding a new mailbox backend and protocol.