In Oklahoma you have three sites:
1) Lake Tenkiller, down the Muskogee Turnpike to Gore. This would mean Crappie Point or the old boat ramp (check out Big Daddy's just outside the park entrance, it's good eatin' during your surface interval.) And boat trips are also an option.
Gene's AquaPro in Gore (Strayhorn Landing) is where we got our OWD and where we get air fills, drop by and say hi! Diving off his dock is a bit murky, but the perchacuda are in full force and there are some objects to explore. You can't really get into trouble at this site if you are new or returning to scuba, but the visibility is nothing to write home about.
www.genesaquapro.com
2) Elmer Thomas near Lawton is where we did some of our AOW dives. The area near the dam was crowded, so we went onto the military base (Ft. Sill) and dove a point just past the playground. Very clear until we did the search and rescue! I went elbow-deep in the mud, so try not to stir it up. Otherwise, it's okay and a nice change. Make the drive to the Meers store for their barbeque and onion rings!
http://www.meersstore.com/
3) Lake Murray near Sulphur and Davis. We haven't been there, but some people from OKC make the trip.
http://scubaadventurer.com/
http://www.scubawizard.com/usa/okla.html
Now for something really sweet -- if you have the time, try the lakes along the White River bordering Missouri and Arkansas. We did three of these last summer and only went to Tenkiller once! Very nice!
1) Beaver Lake, AR, is where our oldest daughter got her OWD. Nice shore diving in the park, ask around. I wasn't impressed with the park itself, and did not like the 45-minute drive from Lost Bridge North campground (although I would go back to the facilities just for a camping trip.)
http://www.swl.usace.army.mil/parks/beaver/index.html
http://www.lostbridgemarina.com/
http://candjsports.com/
2) Bull Shoals, AR, is where my brother-in-law and his family did a diving trip with us. He brought his boat, and it was good! We were at Bull Shoals-White River campground, and take blankets because the fog coming in from that spring-fed river is chilly. Excellent site.
http://www.bullshoals.com/boatdock/padi.html
http://www.scubaadventurer.com/bullshoals.htm
3) Table Rock Lake, MO, is my favorite. We went back twice, and did some of our AOW dives there. Lots of stuff to do during surface intervals, and you must do some night diving for the crawdads! Find out when the perch are spawning -- it was hilarious watching the crawdads chow down!
Alas, Dewey Short (the main diving site) closes down around 10 pm, as does the campground. The deep dive along the ropes was interesting, but most of our adventures were at the shallower of two very nice areas.
Our official night dive was from Indian Point off the dock. If these are crawdads, what do lobster look like! There is also a boat to explore underwater.
http://www.mostateparks.com/tablerock/camp.htm
http://www.scuba-sports.com/
http://www.boatbranson.com/diveshop.html
http://indianpointchamber.com/vp/vacation_planner.html
Well, that will get you started. Do be aware that we were using our 3/2 mil suits in the AR/MO lakes, and either 5 or 7 mils during the deep dive -- the air temps are about 10 degrees colder there! We've been hitting Tenkiller around late May through October, although others can stand the cold both in and out of the water.
Good luck!
Oh, I forgot -- our local community college does Scuba Tuesdays, which means we can get wet during the winter months. It's only 18 feet in the dive well, 12 feet in the swimming lanes, but it keeps the reflexes toned. Check around in Tulsa or Broken Bow for something similar.