I signed up for Gandi this weekend to try out, and so far I've been pleased. Ping time from my house is around 130ms and stable, so it should work out for e-mail just fine. Overall, the dedicated transfer rate instead of a monthly transfer limit is what won me over. While I don't think I'd hit certain limits elsewhere, it's just nice to not worry about it at all. Should make doing offsite backups much easier.
As for spam, the IP I got isn't showing as blocked in any of the major filters, so thats a good sign.
Total cost looks like it will run me $16 a month for the base package, and $2 more for 8 extra GB worth of disk space. I'll probably migrate the boards there as well at some point, just to avoid paying for two different hosting solutions.