Con la aplicación que viene de Google maps creo que no se puede hacer que el mapa rote dependiendo de tu orientación.
Sin embargo, sí que se puede hacer con RMaps (gratis en el market). Lo estoy probando ahora y estoy maravillado con ese programa. Básicamente te muestra un mapa (y lo rota si quieres) que saca online de distintas fuentes (google maps, yahoo maps, openstreet, etc). Pero lo mejor es que puedes (desde el ordenador) generar mapas sacados de google maps, por ejemplo, y después verlo offline cuando quieras.
Si os interesa esto último, echad un ojo a este enlace:
http://jpizarro.doingit.cl/blog/29