The National Parks in any given area are set aside to preserve large samples of the various landscapes, but their boundaries are political, not geographical. There's lots of petrified wood and painted desert outside of those two national parks. As has been demonstrated by links and suggested by experienced travelers, there are lots of areas around Northern Arizona where you can enter portions of the painted desert.
There are good annotated maps and guidebooks to the region, and I would suggest finding one or two of those, then picking up a copy of Historical Atlas of Arizona by Henry Walker and Don Bukin. My copy was printed in 1979, I see that it was revised and reprinted in 1986. A search on Bufkin at Amazon shows a couple of books of his you might be interested in.
Usually the national parks in any given area have excellent books for sale that cover various aspects of the region, so if you want to wait, you could pick these up when you get there. You might want to read ahead (the Atlas is a quick read) so when you get there you can make informed choices on destinations, because there is certainly far more landscape than one vacation can cover!
During my park ranger career one place I worked was in southern Arizona's Organ Pipe Cactus National Monument. It's an entirely different geographical region, though it is also desert. I've been through Painted Desert and Petrified Forest several times. It's a great area.