Svaret beror helt på om du vill ha en bra struktur för sökmotorer eller skapa en enkel design utan extra hänsyn för exempelvis Google och annonser från deras Adsense.
Den bästa ordningen för Google och Adsense i kombination är följande:
1. Sidhuvud (sidtitel, ingen Javascript direkt på sidan utan länk, sidans)
2. Sidstart (logotyp med sajtnamn helst i en H1 eller H2, en bra beskrivande tex om din sida andra eventuella "viktiga" sökord flera gånger på ett snyggt sätt)
3. Snabbnavigation (endast snabblänkar inom samma sida)
4. Sidkropp (allt huvudinnehåll, kanske någon mindre annons)
5. Sidmeny (huvudmeny och sektionsmeny)
6. Extrautrymme (kan fyllas med det mesta utom för mycket Javascript och "hide" DIV taggar, samt eventuellt annonser som på höger kolumn osv
7. Sidfot (ja det vet du vad jag menar).
Varför vissa saker hamnar så långt ner i ordningsföljden berör på att Google inte ska ta dessa som viktiga sökbegrepp i onödan i följdordning.
Jag förstår om du kanske tycker att strukturen är svår att följa utan att designen får lida men detta går lätt att åtgärda med hjälp av CSS stilmall och positionersteknik med hänsyn till olika medier, då kan sidan även bli kompatibel med mindre enheter som mobiltelefoner utan ett större merjobb och enklare att skriva ut från såna sidor med en automatisk CSS utskriftsmall.
Just det Menyn, designmässigt varför inte i mitten på startsidan ?

Annars mer tradionellt funkar det bästa på vänster för de flesta, men som sagt i Strukturen borde den ligga nästan sist (punkt sju ovanför).
Om mitt svar var lite "overkill" i sammanhanget ber jag dig att ignorera detta