I think it'd be fun if there were multiple nonograms that are parts of a larger picture. Kind of like series but completing all of them will show all of the nonograms stitched together. 4 40x40 nonograms would create one 80x80 picture.
Some of the 80x80 nonograms already have way too large a header to be able to comfortably solve. Splitting them up would help prevent having 80% of the screen being covered with the header.
This could also allow for larger pictures without being too overwhelming. There should probably be an upper limit but a 240x240 picture divided into 9 80x80 nonograms could be really nice.
Some clever artist might also be able to use more colors this way. So long as one part doesn't have more than 12 colors.