Get with a fellow who posts here infrequently that goes by the handle
"suds".

Someone here should be able to hook you up.

The wate isn't necesarrily what I'd call warm, but gloves should not
be needed unless you are really cold blooded.

I ususally wear a 3 mm shorty.  Sometimes with a fleece if I've been
diving for a few days.

I would recommend Mike Severns if you are a reasonably skilled and
competent diver.  They don't hold hands but do have some good DMs if
you want to see the interesting stuff.  It's a 12 pack.  Ed Robinson
also gets good reviews.  I have no idea who's left in the cattle boat
crowd.  Mike and Ed leave out of Kihei at between 6 and 7:30 to avoid
the afternoon seas.  Most of the others leave out of Lahina.

Or skip the gloves altogether to be politically correct.  Hawaii is very
politically correct.

A full 3mm should be fine.

Tips are greatly appreciated.  I usually tip $5 per dive.  You may think
otherwise after you see the prices.  Hawaii boat diving is plenty expensive,
especially if you're Canadian.  Shore diving is a cheaper alternative, but
being alone and new, probably not a good idea.  You can go with a DM-led
shore dive, as most of the shops and dive ops there offer one.  That's
cheaper than boat diving but still not free.

The best dive ops there, Ed Robinson's and Mike Severn's, don't usually like
newly certified divers but you can give them a call just in case.  Otherwise
you'll probably be stuck with a larger "cattle" boat operation, but it might
not be so bad.  Molokini is probably where you want to go.  It's somewhat
shallow inside the crater and the water is very, very clear.  Most dive ops
will head there, however you usually don't know where the boat is going
until you show up in the morning.  If it's your first warm water trip,
you'll be awed at any old site they take you to, so don't be too worried
about where you're going.  I did find the trips over to Lanai to not be
worth the effort and you probably don't want to do Cathedrals (the headliner
site there) as a brand new diver since that involves slight penetration.

One different sort of experience you may be interested in is a dive in the
shark tank at the Maui Oceanarium.  They only take 4 divers maximum and run
it just 3 days a week to give the sharks a break, but I just spent a week
with Jim, the guy who runs the dives, telling me all about it and it sounds
like a real good time if you like sharks.  If you go, please tell Jim I said
hi, but don't flirt with him too much since he's married and you have a
boyfriend.  The cost of the dive (again, not cheap) includes aquarium
admission for your non-diving boyfriend and he can keep an eye on you from
the safety of thick glass.  Or if you get real sick of your boyfriend and
family, who don't dive after all so how cool could they be, fly over to
Kauai and join me.  I'll be at the Sheraton.

I went to Maui shortly after being certified.  I dove with B&B Scuba in
Kihei, we dove Molokini.  Their website is currently being updated so
all the links don't work but contact info is there and they have a
discussion group where you might be able to line up a dive partner in
advance if you want:
www/bbscuba.co

The dives were great (we saw a whale shark!) and Brad and Blesi were
both wonderful.  Blesi's a good underwater photographer if you're
interested in that.  I think I dove in a full 3mm in November but I
chill easily.

Have a great trip.
GC