That sounds overly restrictive (not because it is impossible, though). Maybe we can require the area of the convex hull to be at most xx% larger than the original area. But that will be hard to enforce when a shoreline is involved.

I don’t think you can tile convex shapes without leaving gaps.

Sure you can. For example, regular triangles, squares, and hexagons can all tile the plane, and they're all convex. There are an infinite number of sets of convex shapes which tile the plane.

Unless state boundaries suddenly become convex it's definitely impossible. Ignoring state boundaries you have the issue that you need approximately equal numbers of population. It's possible that you can still tile the plane with convex shapes, but I'm not quite sure how to approach a proof (or disproof).

sure you can, but you might not want to go that small.

(simple proof is to turn everything into triangles.)