An octahedron has degree 4 for each vertex, and fits on a sphere. It only has eight vertices though. If you take the dual of a rhombic dodecahedron then you have twelve vertices.
You can expand any of these graphs to an arbitrary number of vertices with the following transformation:
It’s not guaranteed to produce something nice - it certainly won’t locally be squares.
Actually you can just paste a square grid onto each side of a cube (then inflate to a sphere). If you don’t have a vertex on the corners, all vertices have four liberties. This is the dual of the graph from the OP.
It turns out this has been talked about before on the forums.
