Oklahoma---my original home state. It's sandy desert in the NW, thick forest and lakes and hills in the SW, ancient mountains in the SE and rolling hills in the NE.
The Wichita Wildlife Refuge. The Wichitas are old granite mountains that have weathered away into rounded boulders. There are legends of lost caves and even a lost mine, and I know it's true, because when I was a child, someone who'd been working there brought me a boxful of magical crystals of huge size---(laughter here). I treasured those wonderful specimans until we lost them all in a move. Mt. Scott has a road built all the way to the top, from which you can get a great view and sometimes see raptors in flight. There are hiking trails in the refuge to areas you can't reach by car---but please respect the buffalo, which will protect their calves. The cows are particularly touchy during new calf season. Do not, repeat, do not, get between a cow and her calf. They will engage in hot pursuit all the way to your car and into the car if you really annoy them. Not to mention the dent they can make in your door. Do not do anything with a buffalo you would not do with a rhino. I don't know the relative weight, but the inclination is the same.
Elk can also be aggressive, but they rarely let you get close. In all the years I lived in the area, I never saw them. On a recent visit, there they were, out of the park, cropping the grass on the Fort Sill drill field, big as life. I'm told this is a current problem.
The wildlife refuge contains longhorn cattle, buffalo, elk, coyotes, prairie dogs, and the occasional mountain lion or bear. I used to camp here, and can also attest that the mosquitoes are epic. It is under the Park Department. Ask the rangers about the rules and about advice.
Platt National Park, a wooded and nice little park off I-35, special note: has some beautiful little elfin waterfalls, actually travertine terraces, as I recall. I don't know whether these are open to the public, because a casual foot could damage them.
Turner Falls: a pretty area where a waterfall base has become a swimming pool, off I-35. Be careful of the hike along the cliffs---very easy to get off track and fall, believing you're still on the trail. People have broken both legs doing that. Stay to the marked trails. But be prepared for something very special in the way of swimming pools.
Sulphur---another natural swimming site with a flow over low rocks.
The dinosaur museum in Norman, off I-35: a really world-class collection of fossils from the central US prehistory. I was good friends with most of them during my study hours at the old Stovall Museum, which was the former home of these specimans.