Cita: SI no hago uso de frames la solución para navegar por la web es crear una página idéntica en cuanto a menus, etc para cada sección de la web?
Sí, exactamente.
Por lo general el menú será solamente un par de Kb, así que la transferencia no sería un problema grave.
Lo ideal sería que usaras algún lenguaje tipo PHP para incluir automáticamente los menúes y así los tendrías en todas las páginas teniendo 1 solo archivo
Quizás quieras leer esto para comprender un poco más el tema:
http://html.conclase.net/articulos/problemasmarcos
Saludos.