This question refers in fact to an optimization problem: the Polygon Containment Problem, and a particularily difficult case too, because the containing polygons can be irregular, non-convex and have holes. Unfortunately, to my knowledge, I do not think than an accurate algorithm for such a problem has ever been implemented in QGis. However, I will propose an easy alternative that can at least help solving some of the cases.
First, from your initial layer (parcels after building difference), create a Buffer with a negative distance corresponding to half the diagonal of your new building space requirement. For this specific case with a 9 x 10 rectangle, the half-diagonal is
sqrt(9^2 + 10^2)/2 = 6.73 feet, so the Buffer distance is set to -6.73.
The output will be a layer containing all the zones (in green) where the centroid of the new building could be, no matter what the orientation of the building is. Some parcels will collapse into an empty geometry, you can identify and delete them by testing which features have an area of 0 or null in their geometries. At the end, any parcel apprearing in this layer and table are certain to have enough residual space to host a new building, therefore they can be flagged as available. You can select your original parcels by location and save them as a _Parcels_Available_ layer. Chances are several parcels will be identified at this point.
Finally, we can find the parcels that clearly cannot containg a building. We know, from the smallest side of the building, that a minimum of 9 feet of space is required to fit the building. By creating a -4.5 foot Buffer on the initial layer, it is possible to identify those cases. Some parcels will collapse to nothing. In the layer table, delete records with an area = 0 or null. Then, select any parcel than do not contain any of your two buffer layers, with a Select by location of your initial parcels with each of the two buffer layers, with the second selection in add to currect selection mode, then switch selection. Those are parcels that cannot contain a building for sure, and can be flagged and saved as not available (red). The entries left will be those in-between cases, where a much more complex algorithm would be required, to see if a building can squeeze in these parts (orange).
Interestingly, some labeling functions are subject to similar optimization problems. With a bit of tweaking with labels in QGis, I was able to generate the following result, by placing free labels with the rule inside polygons:
Although not perfect, it could be an easy way to make a more educated guess about how a rectangular building could fit. This could be an avenue worth exploring as well.
For demonstration purposes, I used larger values for the buffers and buildings to get more varied visual examples with my dataset.