It is hard to find a good provider at a reasonable price. At the end, I went with Gandi and I am using only IMAP. My wife is using both IMAP and the provided webmail. But please notice that I am based in Europe. I am not sure where the mail servers are located. If you are on the West coast and the servers are all in Paris, then it will not be that fast.