Greg's answer (fly CNX-Bangkok, bus/ferry combo from BKK to Koh Tao) is pretty sensible. Because I am not sensible, and planned at the last minute, I did something a bit different. I wouldn't particualrly suggest following what I did, but it did work out well for me, and maybe some of the other details will be of interest.
What I did:
Fly CNX-BKK, bus from Ekamai to Koh Samet, SCUBA with the guy on Samet, 'direct' bus back to CNX.
-Samet has less rain than many locations on the Gulf.
-Cheaper than Koh Chang, or anything involving flying through Samui.
-Do-able at the last minute or on the cheap (bus-only, almost).
-Samet is fun (to be fair, that probably applies all around).
-Because it is not as much of a SCUBA hotspot (and, probably, because it's rainy season) I got one-on-one instruction from an instructor who's been diving for 40 years.
-The lessons themselves were about 50% more money than the advertised rates on Koh Tao, and didn't include accomodation. (IMO, well worth it for what I got, see last 'pro')
-The diving is probably worse. Visibility was very low (I think it would have been elsewhere due to the weather), but even if it wasn't, I can believe that many other locations would be better. That said, it is still diving, and there is stuff to see; I take Greg's point (re, you*can* appreciate what you're seeing from early on), but I still enjoyed the diving, and will go back. Just adjust your expectations.
-Not as quiet as I'd thought. Probably quieter than the other options, but it's an easy weekend trip from Bangkok, and has a pretty thriving, growing beach bar/party type scene. Up to you if that's a pro or con.
-Thai-expensive. Likely applies to all options, and 'Thai-expensive' is still 'pretty cheap' for many foreigners.
-As far as I can tell, at the moment, the only domestic direct flight destinations from CNX are BKK/DMK, USM, HKT, and HDY (and Mae Hong Son). Otherwise (Trat/Koh Chang, NST/URT/CJM) you need to change (in Bangkok).
-If you do things at the last minute, they get booked and/or expensive, especially on a holiday. Duh, right? And yet, I never learn ...
-As always, there is more than one bus. Both of the ones I took were considerably slower than expected. I thought they would be ~2.5 and ~13 hours, instead they were ~5 and ~17. I know I got the wrong bus to Samet (and there is a right one), I do not know if there actually is a faster bus b/w CNX and Samet (I hope so).
-I called the bus from Samet to book the return trip. They insisted that I couldn't reserve, and would need to buy it in person. This is not true.
-This might be a seperate issue/Question, but 'high season' seems to me to be most of the year. I would call early January 'highest season'. We're in rainy season, now (although that doesn't necessarily mean low season for the whole country, and this particular weekend was a holiday).