Did my PADI Open Water at Big Blue Dahab, in Dahab, Sinai.
LOVED IT! Saw stingrays, octopus-es (whatever the plural of octopus is), amazing corals & fishes, etc. The staff & instructors were absolutely fantastic. Definitely beats seeing the bottoms of swimming pools & quarries. And, at 6'6" with a size 14" (US) shoe, they had fins & a suit in my size.

www.bigbluedahab.com

Dahab is also a great place in general--a really laid back, chilled out, vibe that just grows on you and gets you thinking about chucking your return ticket and just living there (we met MANY people there who did just that!!). Food is not too expensive, you'll love the restaurants there where instead of tables & chairs they have carpets & pillows/cushions to kick back on, right on the sea's edge.

You're also just a few hours from a Sinai climb (give yourself the required time b/n diving & climbing) if you'd like to balance the bottom of the sea with the top of a mountain.

I never want to spend my traveling time taking a scuba course so I got certified in a quarry in Missouri and did my advanced in the Comal River in Texas.
They could have been bummer classes except I got certified from a good buddy who made the quarry fun and the advanced was done with a cool intructor who took us over the spillway in the river on one of our dives. They were both wonderful experiences despite their mundane locations.

I'm thinking of getting a PADI open water certificate on a liveaboard in the Similans in Thailand. Has anyone done this or something similar? Would love to hear any reports or recommendations.

Jonny