A single search box. You type in POIs, the Map is constructed around the search results.
The old Google Maps (the tile based one) was based on the idea of a multi-pane map with gadgets and a side panel of 10 ranked search results, but the map was the same no matter the search (pre-rendered tiles). Search results had to be clicked on the map to get a popup to see what it was. The new Maps is based on the idea that the Map itself is the search result The POIs are rendered directly into the map, just like a specialized paper map. It is based on spatial based exploration and relevancy.
There's a difference between a design disaster and "I don't like this because it is different than what I was used to and I don't want to change" IMHO, the new maps is what Maps should have been all along.