I'd love to see board games use irregular grids, in the way they describe: different cell sizes/shapes suit different kinds of buildings/units.
5 large strips (with 4 macro-triangles each) can form an icosahedron in a fairly sane way.
But IMO the biggest mistake people make is trying to make everything fit on a single square; multi-tile objects are very useful. And at that point, why not make everything take several tiles?
Abandoning tiles entirely in favor of node adjacency can cut memory a lot but requires more thought.
I basically took a square grid and then just randomly displaced each of the vertices a bit to disguise the fact that there is a grid at all. I just wasn't really clever enough to come up with any other way to do deterministic procedural generation.