Pour les menus, c'est toi qui voit.. Si tu maitrises Javascript et CSS, tu peux arriver à quelque chose de très beau avec seulement du texte.. Mais tu peux aussi utiliser des images, pour être certain de l'affichage chez l'utilisateur.. Dans ce cas, n'oublie pas les attributs ALT : je pense que pour le référencement, ça aide..
Pour la largeur du site, je te conseille 760px. Mais tu peux aussi utiliser un pourcentage de la largeur de l'écran (peu préci, et il est difficile de mettre un header en image..). Je te conseil d'utiliser une largeur fixe, inférieur 800px, pour le confort de ceux qui sont encore en 800*600.
En ce qui concerne la hauteur, c'est à toi de voir comment tu organises tes pages...