If you've got a partner: the Sawtooths in Idaho. They're in shape early summer, the weather is perfect, the fishing is incredible, the granite is wonderful, the scenery is superb, and there are (comparatively) not very many people. Take the boat ferry across Redfish Lake to save hiking time.
The Elephant's Perch (any route), Warbonnet (central peak), and the Finger of Fate are all classics in that area.