Hi Anthony,
This is a bit odd if it is indeed worded as you described. Normally you are given cloud tops rather than bases. Are you sure they said "cloud base" at 3000ft? Is it possible they meant cloud tops at 3000ft or, in other words, a broken undercast at 3000?
If there was a BKN cloud layer to 3000ft, then your lowest possible VFR cruising level for 040
oM would be 5500ft. 3500 would not be available to you because you must maintain 1000ft vertical separation from cloud.
If you were going to cruise beneath the cloud layer and it had bases of 3000ft, 1500 ft would be the best VFR cruising level (terrain permitting obviously). Note, if you are under 5000ft AMSL, you can *theoretically* cruise at any level you like as long as you fulfill the VMC criteria. However, you should, wherever practicable, observe the VFR cruising levels even when cruising below 5000 ft AMSL.
You couldn't choose 3000ft since you would not have your 1000ft vertical separation from cloud
Cheers,
Rich