Alright, I am currently re-designing my site because it still uses tables for layout Anyway, while I was working with the new code, I realised that with the CSS I was using, I could place the menu DIV before or after the content, and both would work fine. However, which solution is best for SEO? Should the content appear at the beginning of the HTML, or should the menu appear before the content in the HTML (the location when rendered with CSS would be the same).

Some sites have the HTML for the menu at the beginning (such as w3.org), others have it at the bottom (such as Wikipedia). Which one is best SEO-wise?

Given the choice, such as you have because of the way your page is being developed, I would place the Content first, followed by the navigation.
On a small(er) site, i don't think it is critical, but the larger your page becomes, the less likely it is that the bot will travel deep into your page to find the h1 tags, etc. Earlier in the page is better than later.
Even more important is the use of div's and external CSS instead of tables. It will reduce the bandwidth, sped up delivery, speed rendering, and make it easier to update. All kinds of good reasons to avoid tables for layout, size being one of them
The most important and most effective method to generate good SEO is Content. The three most important features of a site are content, content, content. Good content will work on a bad page. Bad content on a good page will fail.

Alright. I know how important content is for SEO, but at the same time, I hesitated to place the menu at the end, as the links may seem less important for the spider when they are at after the content. The main page would surely get a good rank, but I wondered whether the bots would find the other pages as important when the links to those pages were at the end.