Microsoft XBL Marketplace, Apple iTunes Movie Rentals and DirecTV On Demand which I got a few weeks ago. Most of DTV's VOD stuff is standard def but some of their PPV movies are HD. Movies typically run in the 5GB range and at 30Mb/s I can start watching them immediately after ordering just like cable VOD was.
I read that the Netflix Roku box is capable of HD, but Netflix just doesn't offer the content.