This reminds me that some tourist traps in Baja California Sur, mostly gringo-run outfits in Cabo San Lucas, have started to call the Gulf of California the Sea of Cortez. It actually shows up on many tourist brochures as The Sea of Cortez. That's really insensitive, callous, and exhibits an utter contempt for history. If you really must name a sea after the marauding conquistador that brought smallpox to the indigenous peoples of the Americas, at least do it with the sea that he actually crossed to get to Veracruz. Call the Gulf of Mexico the Sea of Cortez. That's just as callous, but at least it is sensitive to the facts of history.
My vote would be to leave the Gulf of California the Gulf of California (Golfo de California on Mexican maps, of course), and change the Gulf of Mexico to Sea of Tehuantepec (Mar de Tehuantepec.) Or maybe name it after some brave Mejica chief like Nezahualcoyotl or Cuauhtémoc. I love those Nahuatl names, don't you? Coyolxauqui, Huitzilopochtli, Chipotle, Moctezuma. Very chic, imho. Or, if you really want to basque in the warm glow of White Man's Guilt, call it Mar de la Época Triste, or something morose like that.
I vote for "Sea of Tehuantepec." Who's with me?
I'm afraid my vote is no. Tehuantepec is a Pacific coast name and doesn't work for me as a marker on the Atlantic side. The Caribbean Sea is named after the indigenous Carib, so the natural choice is Nahuan Sea named after the indigenous Nahua. Doesn't that just roll off the tongue?