I always thought that the 'level up' part of a space sim would be to do with your military rank - the higher the rank, the more advanced fighter you get to fly. That might be a 'variant' based system, where each variant has different armor, shield & gun specs - and you get to choose the appropriate variant for the job (heavy armor/shield for capship engagements; lighter & more agile for patrols etc.) as opposed to getting just one standard craft in the beginning. That, and later getting to choose which craft to fly (where earlier it is dictated to you). Kind of sounds like the variants in Arena, doesn't it?
The difficulty would be tying into the storyline, and balancing the combat, so that it didn't just become like Privateer 2 (where getting more advanced craft just ramps up enemy difficulty - making it pointless to have anything but the cheapest, most basic craft & weapons).