I recently switched from Gmail to Fastmail.fm for much the same reasons as the OP. Fastmail.fm managed to migrate 30k emails without so much as a sweat.
I still haven't worked out what I'm going to do about Google Reader :(
I still haven't worked out what I'm going to do about Google Reader :(
So far I've loved Fastmail. It's great having a real human respond to a support ticket, usually within a few hours!
Has few bells and whistles (which is a plus in a way - not infected with social disease) but does the basic read and sync quite well.
I've been using Feedly since the Google Reader announcement, and am quite happy with it.