For the Yellowstone part, much of the mid-to-higher elevations will still have snow that early in the year. When you pick up your back country permit, the rangers are usually excellent at letting you know what problems may exist (high water, bears on kills, etc).
An overnight trip into the Hellroaring/Yellowstone River area or Slough Creek area is usually warm and dry by then. There are plenty of campsites and the distances between them are short. Competition for these campsites can be high this time of year.
The Bighorn Pass trail campsite should be open and dry. The views of the Gallatin Range are awesome and you can day hike around the lower elevations.
The Lamar River trail from Soda Creek Butte is usually open but may have a few grizzlies around cleaning up winter kills. Spring runoff may make crossing Miller Creek (if you make it up that far) and others a bit problematic.
The Solfatara Creek to Cascade Creek trail can also be good but has a rep for bugginess during June/early July.
Sounds like a fun trip. We took our kids there at about that age and went on a few hikes and a horse ride, and drove around too much for their liking.
