Depending on how many people are involved, this may take a long time. If you have several people who want to help, turn them loose with themes. For now, avoid themes with too many areas on them: it's harder to switch themes in these cases. If you want, do a test by installing and switching among three themes to make certain you're not locked into an idiosyncratic structure.
Decide on your basic block layout: two sides? header? footer? At the moment, I happen to like a left-nav block, header, and footer.
Basics for left-nav can be:
For the footer, put some custom blocks there such as copyright, etc.
Decide if you want menus somewhere. You can revisit this later. Lots of sites start without using internal menus. Just get some content up there.