I've not been to Bonaire but do have a trip scheduled there in Feb '12. Last March a buddy and I did the Belize Aggressor, it was my first liveaboard. I did every dive the boat offered and got in 24 dives. Some were great - Half Moon Caye being the best and a site called Sandbox being the worst. We voted to skip the blue hole, some had been there before, others, like me, didn't care to miss a couple dives just to drop down a tube. Overall, it was a good trip - I'd do a liveaboard again, but NOT in Belize. You can get to any site we dove from Ambergris and I'd MUCH rather spend a week there and still dive my brains out. The boat and crew were very nice, don't get me wrong, the diving was easy, food was decent. If you do decide to go on the Belize liveaboard, plan to leave Sunday not Saturday, skip the last night on the boat - there are no decent restaurants near the port anyway - and head to Ambergris for two nights. We went to Ambergris on Saturday AM and wish we'd have skipped the "activity" on Friday afternoon and just went their straight away. It's lovely and we could have gotten a couple more dives in!! To directly answer your question - I'd choose Bonaire for sure.
Maybe Utila or Cayman Aggressor would be better. I'm really looking forward to Bonaire though - that pretty much sounds like a liveaboard on land, kinda like CoCo View Roatan which I absolutely loved!!
I'm sure you'll have fun no matter what you choose.