I went with Namecheap as my Gmail replacement. I can use my own domain and setup was instant. The interface and admin panel are very clean which is nice, but $10/mo for one inbox doesn't really say "cheap" to me. Overall I am quite happy, though.