I was thinking about making a custom 3 person play mat (mdf board painted with stars and such) that would be a hexagon, and slightly larger than the standard 3' square. A player would take every second space, and distance from their edge to the middle would be 18" just like regular. ... This would be ideal I think

This is basically what we do, we use 20 and 3/4 inch sides, which is almost exactly 3' from one side to the opposite side, and we set up on every other edge, so no one starts by another person. When measuring, make sure your angles are as close as possible, or that last edge you mark will be off by quite a bit!