Given a restriction of "all areas are at are at least 3-4 blocks wide" the first idea that leaps to my mind is something like the following:

1. pick one of 3x3, 3x4, 4x4 or 4x4
2. place a block of that size in the center of the grid
3. pick a direction (up, left, right, down)
4. try to place a 3x3 block alongside previously placed blocks in that direction
5. if successful, with some probability, try to expand the block to a 4x3 block in one of the directions you didn't just pick
6. with some probability, move a to random edge of the filled in blocks
7. repeat steps 3 to 6 until the area is large enough

The basic idea is, given you want all areas to have at least a given size, only work in areas that are that size. More generally, if you want something to be true of all generated outputs, see if it can be made true of all partially generated outputs.

Given a restriction of "all areas are at are at least 3-4 blocks wide" the first idea that leaps to my mind is something like the following:

1. pick one of 3x3, 3x4, 4x3 or 4x4
2. place a block of that size in the center of the grid
3. pick a direction (up, left, right, down)
4. try to place a 3x3 block alongside previously placed blocks in that direction
5. if successful, with some probability, try to expand the block to a 4x3 block in one of the directions you didn't just pick
6. with some probability, move a to random edge of the filled in blocks
7. repeat steps 3 to 6 until the area is large enough

The basic idea is, given you want all areas to have at least a given size, only work in areas that are that size. More generally, if you want something to be true of all generated outputs, see if it can be made true of all partially generated outputs.