Buy a Winegard Trav'ler. I like DirecTV best due to satellite location and simplicity of setup but make a choice between Dish and DirecTV before purchase as the Dish version of the Trav'ler cannot be changed to DirecTV HD in the future while the DirecTV version of the Trav'ler can be changed in the future if necessary.
You would then be able to install a Genie DVR (5 tuners) and a separate mini-genie at each TV (wireless). Each TV would have full access to any channel plus they would all be connected to the DVR so they could stop and rewind at any time. Dish has a similar receiver called the Hopper (3 tuners) and uses remotes called Joeys.
Edit: Corrected wording.