Thanks for the replies guys. The wife and I aren't in a super rush to find a new place and would actually prefer to take some time and find someplace nice so we can setup and stay awhile.
ratech: PM sent
ken0042: Thanks for the tips, I would appreciate it if you could pass along any other links you might have. One of the places we went to was willing to start our tenancy on the 15th or 16th so that doesn't seem to be as big a problem as I thought. It's just giving notice to end the tenancy without having a new place to move into still kinda worries me...
BlackArcher101: You mean I can't just use the internet for everything? Man, getting out into the real world sucks!