Gallego y portugués vienen del gallegoportugués. Es decir, que hasta un poco después de que Portugal consiguiera su independencia a mediados del siglo XII hablaban la misma lengua, pero con el contacto de la zona de Galicia con el castellano, el mozárabe y el árabe, por el deseo de los portugueses por querer diferenciarse como nación de sus vecinos y al pasarse el centro de cultura al centro de Portugal (antes estaba en el norte, que es donde nace la nación portuguesa), van evolucionando de formas distintas hasta tener las dos lenguas de hoy en día. De modo que sí, su gramática, léxico y sintaxis son muy parecidas, al igual que pasa con el español, de modo que sí se entenderían un gallego y portugués (poniendo ambos de su parte, claro). De hecho yo he ido al centro de Portugal con mis padres y nos hemos entendido gracias a que mi padre sabe algo de gallego.
Y el portugués hablado en Portugal es el portugués europeo, que también es el oficial en los Países Africanos de Lengua Oficial Portuguesa (PALOP), mientras que el portugués que llevaron a Brasil los colonizadores de Portugal adquirió autonomía respecto de la variedad europea, por eso hoy día hablan la variedad del portugués americano. Ambos, europeo y americano, tienen pequeñas diferencias en ortografía o pronunciación. Por ejemplo en Brasil tienen la elevación de /e/ y /o/ (a /i/ y /u/ respectivamente) y pronuncian /amu/ en vez de /amo/ o usan la diéresis a diferencia de los portugueses. Así que sí que hay intercomprensión pese a pequeñas diferencias. Hay quien defiende tener una misma ortografía por ejemplo para facilitar la difusión de libros y hay mucho jaleo sobre todo esto.
Los que no podrían entenderse (ya desde el siglo XVI) serían portugueses y criollos africanos, ya que en en África se crearon pidgins y criollos con el contacto del portugués europeo con las lenguas indígenas y tienen léxico portugués, sí, pero la sintaxis es básicamente de sus lenguas maternas africanas.
Todo esto es por lo que he estudiado, personalmente no he tenido el gusto de poder sentar a tomar una taza de té a un gallego, portugués, brasileño y a un africano, pero sería muy interesante así que me lo apunto como cosas que hacer antes de morir.
