Netflix does have nearly all the NuWho episodes, but I think it's missing Planet of the Dead (though to be fair, it's not really an essential episode to see). You will have to find the specials from after Tennant's fourth season manually, though; they're not with the other Doctor Who episodes, or at least they weren't when I was watching them on Netflix about a year ago. (These occur chronologically between series four and Matt Smith's entrance in series five, and if you skip them you will be completely lost).
Starting with Eccleston and going forth is definitely a great way to do things, though. It's what I did as well. Just make sure you don't skip Classic Who entirely; it's given the name for a reason, as quite a few serials are definitely classics. In particular I strongly recommend The Caves of Androzani and Genesis of the Daleks.