Actually, a triple outlet, if you want OTA - unless you want to wait until the SWM (single-wire multiswitch) comes out, and then you'll need a double, unles you don't want OTA, in which case you could then get by with a single.
It's not that they need it to provide HD. They need one cable for each SAT tuner on the DVR - otherwise you won't be able to watch/record two shows at once. You'd be limited to only having one active tuner, meaning that if you were recording one thing, you wouldn't be able to record something else a the same time, and you could only watch the show being recorded or something you had previously recorded - not something else from live TV.
That changes if you have OTA, because the OTA input does have dual tuners with only one cable. So if you ran one cable for satellite and one for OTA, as of right now you could be doing two OTA feeds, or one OTA and one SAT, but not two SAT, at least until the SWM comes out. If you want to do OTA and would be ok with only one SAT tuner for the short term, I'd recommend running your own cables for the OTA and just going with one feed from the SAT - then you can get the SWM when it comes out and you'll be all good.
The D* installer will run extra cables if needed, but only around the house and through an outside wall, unless you are willing to pay extra for a premium installation to get the wires run through walls, etc - if that's possible at your house.
You're correct that cable only uses one cable run for their DVR's - not sure about Dish, to be honest...