I think the people saying think "small theater" are onto something, but I'd personally want to spin it a little different.
You're in a situation (like I was a few years ago) where you were looking for a house and knew you wanted a home theater. First thing is, IMO, don't get hung up on looking for a certain screen size. Think about the "experience" or functionality you want out of your new theater and look for problematic things for getting that.
In my search I veto'd a lot of houses because they wouldn't work well for a theater. The most common thing was the rooms best for the HT (in the basements) were usually oriented across the length of the house and thus had the HVAC bulkhead directly in the way of where the projected light path would be.
Probably the next big thing is to think about seating and layout. How many seats do you want, how do you want them laid out? My current theater is a bit under 12' wide so I can get three HT seats in and it's long enough that I can get two rows in. However if/when I look for a new house, I'd really like a room more like 16' wide (or more) so I could put seats in 4 across and still keep probably two rows to be able to get a few more people in, and to have a bigger screen.
I guess the way I'd sum it up is this:
You've got a "blank slate", so start with your ideal seating configuration. If you figure very rough numbers, you probably need about 3 feet per seat width, plus another 3 for space to walk by (unless the entrance is in front and you've only got one row), then figure maybe 6 feet deep for each row. Personally I'm a huge CIH fan and IMO the screen should be at least as wide as the seating, so nobody is "outside" the screen.
So if we take my HT as an example. For a 3x2 seating configuration, you need about 12' wide, with a screen say 9+ wide (mine's just over 9'). For depth, you probably want to keep the seating within 2-4 screen heights, so 9' wide (~4' high) means seating between 8 and 16 feet. So you'd need a roughly 12x18 room (need a bit of room for seating and stuff) or so for that sort of theater setup.
If you went to 4 seats wide, that would be 15' wide, about 12' wide screen, so 10-20' seating distance, so it would be a 15x22.
If you go down to 2 seats wide, then you only need about a 9x16 room.
Personally, for my next HT (in whatever house I eventually move to at some point), I'd love probably a 15-16 by probably 25' room with >8' ceilings so I can have a 4x2 seating setup with a nice >12' wide scope AT screen.