I second your Gandi recommendation! Everything is straightforward. Never had any problems with their service or support.

When you buy a domain from them they also include a pair of web/smtp/pop/imap mailboxes you can use, with the ability to create aliases, including wildcard aliases. So I don't need to pay separately for fastmail or some other email service.