Northern Red Desert is the way to go. Not only is the grouse hunting great, you'll probably see elk, definitely see feral horses, tons of pronghorn, and the coolest desert type scenery in WY in my opinion. All while seeing very, very few people off the main roads.
Sage Grouse are well traveled birds, so sometimes you can see a bunch in one place and come back later and not see any. That's just been my experience but others may know more sure fire spots. Draw a hundred and fifty yard circle around Farson WY and it contains a significant number of the total sage grouse in the entire US.
Bring the dogs if you've got em. Not because you need them, most grouse are dumb as a post. It's just good early season practice for the dogs, and they usually hold pretty well. If you want one to mount, don't shoot the first one you see. Wait for a big ol bomber male. After you've gotten used to the large size of SG in general, you'll know one when you see one. They're gigantic, even by SG standards. If you want one to eat, do just the opposite. SG are longer living than most upland game, and I hear those big ol males aren't the best to eat. Ive never tried one, someday I probably will just to test the theory. But get out and hunt them if you have the chance.
This administration has torched the land use plans that kept the SG from being listed a few years back in the name of energy dominance. Listing talk will be right back on the table with the next democratic administration, and this time plans that exist on paper only may not be enough to keep them off the ESA, especially the way this last change in administration has gone in regards to SG. Not trying to be political, that's just the way it is. Moral of the story is hunt them while you can.