We stayed at the Best Western at Panguitch on Utah 89. It is a 20 miles drive to the park entrance and very scenic, especially for sunsets, i.e. after you have done your sunrise shots and doing the Navajo Trail at Brice. Cost is half than Ruby's. In addition you have nearby the famous Steakhouse "Smokehouse Cafe" where Harley bikers use to hang out (in summer).
Have fun, Jurgen