Rectilinear grids are trivial to index, and very fast, but are not particularly flexible.
Unstructured triangular meshes are where it's at. They are very fast to interpolate, and the topological information can be stored efficiently. Triangles can be used directly by graphics hardware without any intermediate steps.
Hexagonal grids are all the rage, but are not numerically interesting. These are good for binning quantities in space. Having more neighbors reduces visual artifacts like striping in the X and Y dimensions.