I can't answer all your questions. I can offer some resources that might help inform some of the issues.
Curacao Trip Research Note
Curacao Trip Report with SB Surge Jan. 2019
In a nutshell, a number of people report the western region has better diving, though I was pleased with the more eastern sites we dove on my trip (I haven't dove the west). If you stay in the Westpunt area, which I'm told is about 45 minutes drive from Willemstad, it's a lot more rustic.
A big issue is whether you'd like to roam around Willemstad much, visit the Curacao Sea Aquarium and so forth. If you want to commit one day to that, then where you stay is less important.
Caymans = Grand Cayman, Little Cayman and Cayman Brac. The first is a cruise port, the latter two are small, rustic islands. Grand Cayman is probably the closest to an 'apples to apples' comparator to Curacao, as it's got boat and shore diving (so does Cayman Brac) and a range of topside activities.
The Caymans have a rep. for being expensive, but roundtrip airfare and car rental can be surprisingly affordable from what I'm told. I've read good things about Turtle Nest Inn packages (granted that's in Boddentown, well away from 7-Mile Beach), and if you want 7-Mile Beach proximity, I've read good things about Comfort Suites and Sunshine Suites (as budget options).
Richard.