The Flower Garden Banks are not for beginners. I've logged over a hundred dives out there and used to be amazed that the dive shops would sell spots on the boat that I crewed to people that had never dove in saltwater. It made me furious because they simply weren't ready for open ocean diving 100 miles from shore. And it was a miserable experience for them because they just weren't ready.
The Gulf of Mexico has some awesome diving. Some of the best dives I have ever done were right off of our coast. But get some experience in places like Cozumel, Grand Cayman, Bonaire, Roatan, etc. before you go to the Flower Gardens. You'll have so much more fun there once you are really comfortable in the water. The rigs can also be challenging if the water is green and the currents are strong. If you are new to diving, try to go in July, August or September when the currents die down and the water is bluer.
I'd recommend American Diving on SPI as a first GoM dive. His boat will make you seasick, but the Texas Clipper is a good dive. And the owner is a longtime NAUI instructor who is very respected. He runs a good operation. Just wear a patch and it'll help with the boat and getting seasick.
And FYI, the Flower Garden Banks aren't terribly deep, they just have challenging conditions. (Get NITROX certified before you go out there!)
If you really get into diving, there are some awesome dives right here in our backyard.
