Here's a fairly brute-force algorithm:
Scan across each row, left to right, top to bottom, until you hit an
unoccupied tile of the correct type. (You can skip the far right columns/bottom rows once you get too close for the placement to fit)
Once you find a valid tile, check all tiles that would be within the placement footprint, if you put the top left corner here. Start with the tile furthest away (the bottom-right corner of the placement), and gradually work back.
If you find an invalid tile (wrong type/already
occupied), mark all tiles in the rectangle containing your proposed top-left corner and the obstacle as "explored", and resume searching with the
next tile after the proposed top-left corner.
As you continue your main scan, skip over any tiles marked "explored"
If your search in 2 does not find an obstacle, return your proposed top-left corner as a valid placement and terminate.
Steps 3 & 4 are a small improvement over straight-up brute force search, in that they keep you from repeatedly checking the same patch. Starting from the opposite corner lets you skip as many tiles as possible using this trick.
If you need to improve on this (profile, to see if it's worth your trouble), you can keep a bit of helper data with each tile: the size of the largest unoccupied square of the same type with that tile as its top-left corner.
Fill this data in once during map generation, by brute force if need be, then update it any time a tile changes state (search a rectangle up & left of the changed tile for any tiles that count it in their largest square. Decrease their largest square so that it ends just before the changed tile. You can end this search early once you've gone as far as the widest placeable item in your game.)
Now you can find a rectangle of the right size with a linear scan of the map. You can shape this scan any way you want - say searching an expanding spiral out from the focus of the player's current view, so that you can minimize the camera move required.
If you need even faster lookups (doubtful), you can use this data to sort your tiles into a heap (or series of heaps) by largest-placeable-area. Then in a O(1) operation you can pluck out a tile big enough for a given placement, or correctly conclude that none exists. (Just watch out, if you always choose the biggest-available area, regardless of the size of the placement, you'll tend to fritter away your wide open space on small placements)
That kind of acceleration structure can be expensive to maintain though, so only do it if your searches for placeable areas are causing noticeable problems.