I tend to prefer hexes all around. Ya, sure it's harder to draw perfect-90-degree grids of streets/buildings/rooms, but if you look at real-world examples grid layouts for cities are a recent thing. Mathematical layouts for the interior of big buildings (especially temples/cathedrals) goes back farther, but this tends to be a matter of "where do we put the supporting pillars" rather than "we like 90-degree corners". Just eyeball it, like a real medieval builder.
I've occasionally seen maps done in "staggered squares" - a grid with every other row of squares offset 50%, like bricks. This gives you movement/facing like hexes, but nice square corners for the Jello-cube lovers. Unfortunately you can't get the big office-supply pads (but then, you can't for hexes either), and battlemats are hard to find.
The only times I've had to "zig-zag across the map" have been when playing Star Fleet Battles; in RPGs it hasn't been a problem, I think partly because with hexes you have six directions of "straight-line" movement instead of four, so there's less need for "diagonals" unless you need to Charge an enemy who's barely the minimum distance away.
OTOH the giant presentation pads are nice, especially the ones that are a giant Post-It note so you can stick them to the wall.