There are two ways to grid a map for game play. The Cartesian grid is very familiar, and easy to access, given our familiarity with graph paper. But rules for movement are more complicated when figuring out diagonal moves on a rectilinear grid. So, the other alternative, which was taken up by wargamers decades ago, was to use a hex grid. Hexes are the other geometric figure that can tile the plane regularly. And there are no issues with diagonal movement with a hex grid.
But I’ve been kicking around some other ideas for a while. One easy adaptation that is midway between hexes and a square grid is to stagger the grid cells. A half-cell offset in the rows of squares gives you the same overall orientation and even tiling as a hex grid, but with fewer of the non-perpendicular lines that may be what makes hexes daunting for many people.
To make the lines more distinct and readable, this version turns an overlaid square grid at a 45 degree angle, so that the two grids are both readily identifiable without overlapping one another.
The scale for this is the smaller (hex-replacing) squares are 4′ on a side, so the larger, diagonal squares are then slightly more than 11′ on a side. I think that’s workably close to a 10′ D&D dungeon square overlaid with a 1-figure sized space
Edit to add (12/22): Of course, I am an idiot, and these should not be true squares in order to evenly match a hex grid. But, for most purposes, I think it’s simpler and easier to do the basic running bond squares as “good enough.”
Edit to add (12/22): Stephan Beal followed up with this comment on G+
By sheer cosmic coincidence i stumbled across an article in Space Gamer Issue 30 this morning which places an exact year on the introduction of the hex in games:
>>>Hexes in wargames go back to 1952, when they were used in some of the government-sponsored “think tanks.” In commercial wargames, hexes were first used in 1961.<<<
Space Gamer issue 30, page 20: