It sounds like an interesting trip. While in the Rushmore area, you might like to check out the Mammoth Center in Hot Springs SD. From there I would head toward Greybull WY and on to Cody. Plan to do spend a day or two exploring the Buffalo Bill Center. That one is a "must do" if you are in that area.
From the south entrance of Yelliwstone, you can head south through the Tetons and Jackson Hole. Heading south from Jackson Hole will get you to Flaming Gorge. If you are interested in dinosaurs, Vernal UT is a good stop.
These are all decent roads that are not in any way close to being an interstate...or even something more than a two lane highway. I will leave it to our members who travel further south to make recommendations on roads and stops on down from there.
Have a great trip!