Since we need to use hookups, our favorite CG for the Tetons is Colter Bay RV Park. For that one and for anything inside Yellowstone, you will need to make reservations as far ahead as possible (up to 2 years in advance for Yellowstone). Fishing Bridge CG is the only one inside Yellowstone with any hookups at all, and they are still closed through all of next year, to my knowledge (getting a major redo). West Yellowstone is a good base camp for Yellowstone - several good private CGs and a 1st-come NFS CG there, and much closer to the entry gate than CGs south and east of the park. Late May/early June is do-able, though not all CGs may be open if there is too much snow. I believe the private CGs in West Yellowstone will be open by then, however.
I like the Colorado suggestions you've been getting. Not sure where you have been, if you said you have been to 4 Corners area, but there is a ton to see in sw Colorado and se Utah - if you have missed either of those areas, it would be worth your while to catch up with it this time.