Gulf side I lived on koh tao last year, I can recommend personally Asia Divers, the manager is Guy Corsellis. They are not too big a dive centre and have good, friendly and knowledgable staff.
I particularly like chumpon pinnacle as a dive site as you can always see large pelagic fish, in particluar around barracuda rock (a particular part of the dive site). Other good sites here are southwest pinnacle, similar species to chumpon pinnacle. Red rock is another good site, as is green rock, both of which have some beautiful triggerfish.
White rock is great on a night dive when some of the bigger species come close inshore (and the triggerfish are sleeping then too!!).
All of the dive sites can be done by open water as you can pick different parts of the site according to depth / ability.
If you're looking to travel to koh tao there are several options, the cheapest is to go to koh sarn road (Bangkok) and get an over night coach which includes ferry cost to the island), alternatively you can get a train from BK down south to Chumporn and then get the ferry across.
The quicker but more expensive option is to fly from bangkok to koh samoi and then get a ferry to koh tao.
if you need any further details send me a message, thanks
Greg Jenkins