Fast algorithm to distribute points evenly in a 2D grid
The optimal centroidal Voronoi tessellation for the infinite 2D grid is a hexagon tiling.

You can get one of these by placing points at even coordinates on even rows and odd coordinates for odd rows. Depends on the number of points you need.

Start with that then run Lloyd's algorithm for a few iterations to tidy up the corners and edges.

I would compute it offline on a unit square to good precision, then dilate it to your chosen rectangle with a simple linear transformation.