Another idea strikes my brain today, and stuck to a few other fragments hanging around in there. I'd be interested to see what people think of this. Two main questions would be whether its interesting enough for people to play, and original enough to be different from what's already out there.
The plot (if required) would be something along the lines of a great cataclysm erasing significant portions of the world. Only in highly populated areas was people's knowledge/imagination of their surroundings strong enough to keep places real. Everywhere else, nature dissolved into a grey blank canvas. Now it just happens that you're one of the few people with enough imagination to recreate the featureless world. Or maybe it could work without an RPG type plot, and be more like a pure puzzle game.
You start with 5-6 'tiles' in your memory. Maybe they're bits of countryside you remember or something. Each tile would be a 3x3 block of map tiles, with roads going out on 2 or more edges. Next to a city (like the one you start in), you can place any of the tiles from your memory. Once you're walking along a road, you can only place tiles where the roads and terrain along the edge of the tiles match up. To start with, you'd have tiles with just grass or desert terrain, and either 2 or 3 edges having a road coming out along them. This restricts you to a relatively small subset of the possible tiles, so its relatively likely you'll have one to fit in a certain place.
On the 'blank map' or on certain tiles, you'd have a couple of types of resources. These might be imagination wells, or settlements. If they're on tiles, you can put them down and visit them as soon as you have a matching tile to put them next to. If they're on the map, then you have to get to them and put a tile on top of them, and the relevant object appears in the centre of the tile.
Imagination wells are little bits of grey that aren't entirely clear. They might be mis-shapen representations of what was once there, like modelling clay that hasn't quite been rolled flat. They can stimulate your imagination, like seeing faces when you look at clouds. Collecting one lets you take a tile from the available set into your memory ~ draw a card, essentially. They will 'respawn', scattered randomly across the map area you've already explored, after certain events.
Settlements are little villages - maybe without the people, but small enough for you to envision them on your own, or that might have barely survived whatever weird apocalypse has struck this world. The number in your 'deck' will be quite small. I'm not sure if the ones on the map will be in predefined places or scattered randomly, but the number will have to be fixed. Each settlement has a mini-game attached; a falling block puzzle, or snake game or something. I'd say these should be all different (though there's at least a few variations on the theme of block puzzle), hence the fixed number of villages in the game. Maybe these will use the same graphics as the main game, or maybe they'll be more abstract. Some of these may require you to achieve certain milestones (level, points, etc) before you can pass through. All will have a game-specific list of achievements to pass, and let you draw another tile for each one completed. Some will have only 5 levels, or 10; while others might just go faster and faster, and hand over a tile at regular intervals as long as you keep getting higher scores with no arbitrary limit.
For a little extra 'bonus', maybe the settlements will grow more ornate on the map, covering an entire tile rather than just the centre square, as you get better at the game.
As far as the 'RPG plot' version of the concept goes, there are also larger towns, with people in, who further some kind of "restore the world / prevent a second apocalypse" plot. These cities will be much like the place you start in; most will have a few inhabitants to chat with, maybe some items to spend your points on, and (assuming enough development man-hours to provide sufficient games) a game or 2 in much the same way as the smaller villages.
Cities would be placed in a pre-defined layout; as they're linked to a game's story, it wouldn't make much sense to encounter them in a different order.
Items could possibly include 'game powerups' like a bomb (usable in most falling block games), a shrink potion (shortens mr snake, or flattens a tetris-piece) or speed up/slow down items (which could be used in most games, but would only be advantageous in some). You could also have game varying items, such as one which makes the playing field 4 squares wider (for most games with a randomly generated board). For some games, a created variant might turn out to have its own set of tile-yielding achievements.
One addition would be a book (not sure if that's the best item) which lets you learn about a new terrain type, or a new road type (get a boat and you can travel along rivers too): now, each tile edge can have two paths leading off it, one of each type, which makes it harder to find a match, but then that is balanced against the growing number of tiles you have in your memory. When you get a new path/terrain type, you can choose to discard and redraw tiles in your hand, from the new expanded deck. Maybe there's a good chance you'll get back tiles with the road in the same place, but with a river on it too, or similar. Explore far enough, and do well in all the mini-games, and eventually you'll reach enough cities to complete the story; but a game like this should have enough replay value to keep on going with the mini games.
One idea I had as a possible extension to this would be as a mobile game; play within range of someone else (I believe they've got a mechanism for the 3DS to do something like that, though its probably beyond homebrew guys) and they might exchange minigames in the background. You could have a new minigame injected at any point, and the more you socialise with other players, the better the chance you'll have something new to play. Could even add whole new side stories ... add a bit of variety to subsequent play-throughs.
If a big company was doing something like this, you could have access points at game shows or in particular shops handing out new modules when you get close; I'm sure this could lead to guerilla-marketing monetisation. (Imagine a forum post on gamefaqs or somewhere, "I just got a new mod while I was in Shop X" is bound to drive a few people in)
Got a couple more add-on ideas for this one, if anyone's interested, but its 6:10am now and I should really go to bed.