Patience. It's Super Bowl Sunday and many have headed out for parties.
First, are you talking about beach diving or boat diving? From a boat, there are many dozens of wreck sites to dive. There are a few dived by charters in Destin but most of them are in the Pensacola area. There are also some off Panama City but that's a few hours away. From the beach, I know of no wrecks in the area. There are a few small wrecks off Gulf Shores but the sandbars have mostly covered them up right now.
But there are some good beach dives along jetties and piers where you can find plenty of marine life. Navarre Beach pier is a nice shallow dive where you often find rays, octopi, and many other reef fish. Destin jetties is also a favorite spot. In May, water temps should be low to mid 70's.
Navarre Beach is a nice place to stay (scenic, less crowded, cheaper) and centrally located between Destin and Pensacola, each within 30 minutes. Unfortunately, I think you will have to go to one or the other for dive shops.