We're a bit east of you (Tarboro) and have taken that route a number of times. Petit Jean SP in AR is worth a day or two but it looks like you're pushing hard with just overnight stops on the way out so may not be worth it. I'll second another poster's recommendation of Palo Duro SP outside Amarillo and not too far off I-40. Red Rock Canyon SP in OK is near I-40.
If you have time, try to work Carlsbad Caverns NP in and make advance reservations for the Lower Cave tour. Brantley Lake SP is a good place to stay while in that area and the Living Desert Zoo and Gardens SP is nearby. We found lots of dry camping options around Glen Canyon NRA if that's of any interest.