http://www.gandi.net/ : 1 GB IMAP account included with domains - hosted in France. Another alternative (hosted in the US) is FastMail (see my review here: http://blog.workhere.io/my-experience-with-fastmail-as-a-gma...).

As for IMAP clients, I like http://airmailapp.com/.