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.