I support Brigades because they are the smallest reasonable strategic unit. I think the division should be the basis as Johan has informed us, but that Brigades should be able to have independent movement. At least we should be able to use mini-divisions so that rear areas and coasts can have a more realistic and balanced force, rather than the stacks of full-size divisions HOI2 required for these brigade sized tasks.
I support the idea of composing your divs with brigades. But I don't like the idea of having them as separate units. It would be a heck of a micro.
Maybe, when you order a division to cover the coast, it can "stretch" itself and to deploy its brigades in 2-3 provinces.
I think that that will prevent the micro, but will allow the minors to coup with the increased number of provinces and use one div to advance on a bigger front.