I also started with "And Then There Were None" and moved on with a few that sounded interesting from the title, like "Death on the Nile", "Cat among the Pigeons", "N or M", "Cards on the Table" and "Murder on the Orient Express". All of these I would definitely recommend, as they are some of my favourites!!
Reading book after book I finally realized that there was some kind of continuity between the books (even if it's never more than Poirot saying things like: "This is just like THAT case back then, but different!" so I then started to read her books in the right order.
There really is no problem with reading whatever book whenever you want. There shouldn't be in any way a problem when jumping right into "A Murder is Announced" if you want to.
I am half way through her works and I found each and every one of them worth the read. Some start a little slow, but by the end I was always satisfied. Agatha Christie is an awesome writer and I really have to thank touhou for making me read her books!