Here's an algorithm that might do what you want.
1) "Seed." Iterate over your map in small chunks, e.g. 6x6 tile/pixel chunks. In each chunk, randomly pick a tile inside. If it is land, assign it a new, unique province ID.
2) "Grow." Once you've done that for the whole map, iterate across the entire map repeatedly. For each tile that does not have an assigned province but is adjacent to at least one province, have it adopt the province of a random cardinally-adjacent tile (or any adjacent if you're using hexes). Repeat this process until you walk the map and find no unassigned tiles that have at least one assigned neighbours.
3) "Sweep." Remove all land that has no province assignment at all. These are any islands which you didn't hit during the seed step.
4) "Inspect." Walk the map and get data for every province. You'll want to be able to take a province ID and look up its total area (how many assigned tiles), a location inside its borders (any will do; top-left, original seed location, whatever), and any other data you want to track about them at this stage. You'll also want to generate an adjacency map at this time.
5) "Prune." You'll probably have some provinces too small for your purposes, which won't be able to grow in the next step. For each province under a size threshold which also has zero neighbours, turn it into water and discard the province.
6) "Conquer." At this point, the average size of a province is going to be around the 6x6 area (remember the chunk size, in 1?). But you'll have lots of variety in size and shape everywhere. They will all have grown into irregular, blobby shapes. Now what you should do is start fusing these micro-provinces together! Start randomly picking provinces from the bottom 25% or so of them when ranked by size, and have it merge with a random neighbour. Overwrite the neighbour's tile assignments with its conqueror's, union the adjacency sets, and re-insert the new larger province in the rankings. The wider the conqueror selection is, the more variety in final province sizes you'll have at the end.