Update:
I've got a level generator working! It lays out a maze using Prim's algorithm, then replaces each cell of the maze with a randomly-selected prefab chunk of tiles that has the correct number of exits and entrances (currently I have 3 possible chunks per orientation, for a total of 48 prefab chunks). I also store the layout of the dungeon as a tree, and place the level exit and the key to the exit at 2 different leaf nodes.
You can travel through each level, collect the key, unlock the exit, and climb the stairs to the next randomly generated level. That's enough to technically make it a game I think.
Levels can be as big as I want them, but somewhere around 8-12 cells feels about right I think. I don't know what else I'm actually going to throw into the levels except randomly placed enemies and loot.
I'll probably do the Persona 4 thing and have most floors be randomly generated, but with story-important floors premade.