They accept Amex and will auto-renew. They're $9.99/yr (or within a few cents of that) and that includes private registration if that's something you're looking for. I've had no problems with them, their interface isn't perfect, but it's a lot nicer than most registrars' systems that I've used.
Now for the bad. They don't offer DNS service without a hosting package. I actually use NameCheap's DNS. NameCheap (being kinda a stand-up company) offers free DNS service to you even if you aren't their customer. And, frankly, their DNS control panel is nice enough that I would switch to them, except for the fact that they don't auto-renew and they charge extra for private registrations.
If you don't need DNS, DreamHost seems to work nicely. Decent control panel to make changes in, private registration included in the fee, auto-renewal, $9.99 price, and accepts Amex. It isn't their primary business, but they are ICANN accredited - and they aren't that small (http://www.dotandco.net/ressources/icann_registrars/details/..., see New Dream Network - not that far off from Name.com or Gandi).