I have to say Oahu.
Of course, it's the only island I've been to, so I might be a little biased.
I would suggest
www.oahuscubadivers.com (justleesa is a mod here- she is OSD's Lisa on the site) since your dive expereince is limited. Lisa and Roger are fantastic- very personable and knowledgeable. I spent 3 mornings with Lisa and one evening with Roger and it was all extremely enjoyable. I have been diving with very few dives in the past and I think, after having dove with Lisa and Roger, I'd have had better experiences had I done my early "vacation" dives with them. This time around, I had 63 dives under my belt before getting to Hawaii- and I still felt as though I were a brand new diver. Ocean diving is different from quarry diving- and their expertise took away any concerns I had.
Okay, so just a little unabashed plug for my favorite Oahu dive op. They will go out with just you and your wife for about the same price you're going to pay any other dive op I looked into. And they will give you a mini logbook- designed by Lisa- and provide stamps to put in your "description" section- they'll tell you the names of all the fish/creatures you saw but didn't know what they were AND provide a stamp for many of them so you remember them when you re-read your logs! Lisa drew the pics for the stamps. She's really talented. AND she will make a box lunch for you (and your wife)- it's like kindergarten- stamping and a lunch box! But she makes some killer sandwiches! Perfect for a post dive lunch at a beach park!
They didn't have any other clients when I was there so it was just me and Lisa or me and Roger. MUCH better than a large group- trying to keep from kicking someone or being kicked sucks!
Whichever island you go to- keep in touch with folks here. You may be able to do some shore diving- which is certainly much cheaper than boat dives. I hit Oahu this September right as the conditions on the north shore were changing to strong surf (surfing competitions on the north shore during the winter months) so I only did one shore dive. The summer is the time to do shore diving on the north shore of Oahu.
I am sure the other islands offer wonderful diving, too. But there's something to Waikiki. I'm sorry, but sitting in Duke's listening to the ukelele music, watching the surfers and the surf... it's quite magical.