My short answer is any mail provider that supports IMAP except for Google or Apple is your solution.
Apple's mail app works best with standard IMAP services, so iCloud is out since you can't bring any email except @icloud.com / @me.com / @mac.com to that service.
Gmail is out due to the non-standard breakage that many are experiencing due to Apple/Google's combined inability to play well together.
So, you are left with pretty much any other implementation of IMAP mail that exists as a good technical option for you. I've had good luck with http://gandi.net IMAP email for years and have heard nothing but raves from people that use http://fastmail.fm but you could pretty much pick any company that meets your desire for price, support and features and find that IMAP is really IMAP on Apple's Mail.app for iOS and Mac and the only pain point is between gmail's IMAP/Exchange history assuming that you don't ever want to go back to larger pain that was POP3 access for mail.