First of imagine a board of chess. Every square symbolizes a different area on the map, which each contains a bunch of stars and planets. For example, in the top right corner (if there even is a border; I haven't expanded that thought) is the mantis kingdom, which may be hostile towards the other nations, whereas somewhere else the Engi have built their empire and so on. So every square is being controlled by a nation; there might of course also be uninvestigated or uninhabited places on the map, maybe hiding another evil nation.
This would allow for some kind of story mode. Bad plot I just thought of: You are a young man who visits a big planet and is then drawn into some kind of intrigues or something like that, or you are just joining the army of your nation and because of your good navigation skills you get to control a ship and have to do some missions. Or you are a delivery boy at first and get into some adventures in space
While doing your missions, the evil nations may expand on the map as well as some renegades from other nations, which you will meet (and fight) in space.
Since I am a fan of the rogue-like elements in FTL, a "normal mode" as we know it should be there as well, but still include the map sceme from above. Essentially, there could be many different mini-storylines. You get to chose one in the menu, then chose your ship and depending on your route on the map to your destination, the areas you see are always different.
If this worked, it would mean a lot in respect to 'having a small universe to travel in', but the right way to do it is difficult.
Edited because someone felt the need to correct me, rather than contributing to the discussion. My #1 language isn't english, so I'm terribly sorry for any mistakes:P
A main quest for the middle (or edge) of the galaxy.
