Rapid City to Yellowstone
You would be hard pressed to do better than just using US-14 as your route of choice. It would take you close enough to visit to both Devils Tower and the Little Bighorn Battlefield, And although it's duplexed with I-90 for short stretches, it enters Yellowstone from Cody via the scenic North Fork Highway through Buffalo Bill State Park and Shoshone National Forest.
Whether or not to include Granite Hot5 Springs in your itinerary is entirely up to you, It's certainly on the way to Bear Lake, your next stop, but will eat up some time.
AZBuck