uhmm, si quieres cambiar tan radicalmente la forma de navegación en uno y otro dispositivo casi será mejor olvidar lo de usar el mismo documento con 2 hojas de estilo.
podrías hacer 2 versiones, una para pc y otra para pda, y utilizar php para redirijir a la adecuada dependiendo de cual sea el navegador.
la otra opción, aunque no soy yo muy partidario del uso de frames, es añadir el menu en la página que contiene los 3 frames (con el elemento noframes) para que se vea directamente en los navegadores que no admiten frames, en lugar de un link a los 3 como te sale ahora.
Código HTML:
<frameset (.....) >
(.....)
<noframes>
<body>
<a href="formulario.html">Formulario</a>
<a href="formulario2.html">Formulario 2</a>
<a href="formulario3.html">Formulario 3</a>
</body>
</noframes>
</frameset>