Thanks for your input, Kylotan.
I've been trying out the options in this thread and so far it seems a combination of a (small) bsp-tree and what Kylotan described seems to give the best results. It will require some tweaking still but it's going in the proper direction, and I'm confident it will turn out the way I want it too.
Basically what happens now is that the grid is split at least two times, to make four different sized sections. This is to prevent long streaks of similar sized blocks in the next step.
Then randomly placed horizontal and vertical walls are added, and the resulting rooms are somewhat randomly merged.
This starts to look like the picture above, but there's still a bit of noise and jaggedness because my merging decision-making isn't optimal right now.
But I can work from here, thanks for help everyone!