Depending on the time of year, I'd vote for Kodachrome Basin. Probably pretty hot in the summer, but not too bad the rest of the year -- it is almost 6000 feet in elevation. This was taken from our campsite last November -- we illuminated the spire with a flashlight during a time exposure:
There are almost no lights in the campground itself, except near the bathroom -- and the campground is so spacious that the light is not a problem. The entire area surrounding the park is pitch-dark. There are a few trees, but they are short and spread out.
If you want to get into the higher elevations to stay cool, Bryce or the North Rim would be good. The only problem in the high country would be the bigger trees, getting in the way of the view from the campsite.