The panhandle of Florida may have the best cat sailing conditions and greatest concentration of cat sailors anywhere, and St. Joe Bay is at the eastern end of it. To carry it further east, the stretch of coast from Panama City to Cedar Key still has lots of adventure sailing opportunities. In most areas, you will be able to see the shallow water with sea grass beds.
I've sailed a leeboard monohull (SeaPearl 21) in St. Joseph's Bay. I launched from the city ramps in Port St. Joe, which are quite nice but will give a sailboat trouble if there is a wind directly from the south-you'll have to short-tack down the channel. The water is certainly deep enough for any beach cat that I know (I have an A-class cat with 2.5' draft with the boards down), and I always wondered why there weren't more beachcats in the bay. But then, Port St. Joe is an old paper mill town with small population and high unemployment. They have other things to do than to sail. The mill is closed now, and the bay is clean. The other poster is right - the north half of the St. Joe Peninsula is a state park, and has mostly deserted beaches. I don't know the rules for beaching boats, but nobody else showed up the time I was there. I also don't know about beach access but if my memory is correct and you have beach wheels, then you shouldn't have any problems. The bay will always have flat to light chop water regardless of wind conditions, and the outside is more thrilling but still usually easily navigable with a small beach cat.
There is also terrific cat sailing about 40 minutes to the northeast in St. Andrews bay at Panama City. Carl Gray Park at the east end of the Hathaway Bridge that links Panama City with Panama City Beach (yes, the site of "Girls Gone Wild") is the headquarters of a lot of cat sailing. You can sail to Shell Island where you can find deserted beaches most of the time. There is a seasonal series that is described on the Catsailor events calendar. Maybe you can hook up with some of the PC catsailors. If you don't take your boat, there is a place in PC Beach to rent Hobie Waves - I forget the name but it is in the phone book.
Have fun on your trip, and do take your boat if you can.