This is the recurring issue with 3D space shooters - space is big and empty. Which pretty much removes all the gameplay-enhancing features one expects out of level design: obstacles, choke-points, etc.

Asteroids are a popular choice, you don't actually need very many if you make them big enough. 10 big asteroids typically have more impact on the gameplay than 100 tiny ones. Depending on the scale or level of realism you are going for, various spatial anomalies can be useful as well: gas clouds/mini-nebulae to hide in, wormholes to teleport around the map, black holes to suck players in...

In a more realistic setting, if you don't have the resources to model them by hand, you can procedurally generate space stations. Procedural generation is also good for distant planets, wrecked spaceships, you name it!

@swiftcoder: I tried to click on your link, but it brought me to a blank page. Can you check that?

Give it a while to load - it's typical Blogspot page loading fun.

I would either need some sort of procedural asteroid / nebula / objects of interest generator / deleter (expensive)

These are surprisingly easy to build - you effectively just teleport asteroids from one side to the other of the player when they get too far away. Randomise the location a little, and hey presto, infinite asteroid field.

I would expect the game to consist of

• basic dogfighting in empty space
• dogfighting with obstacles and cover
• strafing or bombing, approaching large objectives from specific directions
• chasing enemies, or being chased, through challenging obstacles (the better pilot increases difficulty and the worse pilot crashes, Star Wars style)
• racing towards some objective, with undesirable delays such as obstacles and enemy fire

While a surface setting is a rich source of landmarks and varied objects for these applications, as suliman suggests, you can extract a lot of value from realistic and easy to make deep space stuff:

• spaceship formations, to ensure variation in battle situations even in empty space
• large spaceships, good as obstacles, objectives, landmarks, and enemies in their own right
• fields of rocks, usually huge ones that cannot be exited before winning the battle; density and special features provide the necessary range of different danger levels
• man-made debris, with a similar role as rocks but present in other locations (satellite orbits, near space stations, etc.)
• medium asteroids (significantly bigger than typical ships) as landmarks, cover, and even military objectives (they can have surface to air weapons)
• large asteroids (without significant gravity) to provide the same tactical situations as a planetary surface mission with cheaper graphical assets
• distant and not so distant planets in the background as landmarks

You should probably design your levels as definite missions, i.e. not loitering around and waiting for enemy waves to appear out of nowhere. For example crossing a blockade, shooting down a convoy, escorting a ship, and other reasons to travel with a purpose and accomplish something clear.