The missing parts don't really have anything to do with the nebula though. The FS1 style nebula uses that stuff, but it is/was part of the 8-bit interface code. And what we are talking about having to add here is something like this (with a minimum of 27 different versions by default):
#define NUM_PALETTE1_01 768
char gamepalette1-01[NUM_PALETTE1_01] = {
'00', '00', '00', '07', '00', '00', '0F', '00', '00', '17', '00', '00', '1F', '00', '00', '27', '00', '00', '2F',
'00', '00', '37', '00', '00', '3F', '00', '00', '47', '00', '00', '4F', '00', '00', '57', '00', '00', '5F', '00',
'00', '67', '00', '00', '6F', '00', '00', '77', '00', '00', '7F', '00', '00', '87', '00', '00', '8F', '00', '00',
'97', '00', '00', '00', '13', '00', '00', '27', '00', '00', '3B', '00', '00', '53', '00', '00', '67', '00', '00',
'7B', '00', '00', '93', '00', '00', 'A7', '00', '00', 'BF', '00', '00', 'D3', '00', '00', 'E7', '00', '00', 'FF',
'00', '00', '3F', '00', '00', '7F', '00', '00', 'BF', '00', '00', 'FF', '00', '1F', '00', '00', '67', '00', '00',
'B3', '00', '00', 'FF', '00', '00', '3F', '00', '3F', '7F', '00', '7F', 'BF', '00', 'BF', 'FF', '00', 'FF', '00',
'08', '10', '10', '18', '31', '10', '20', '39', '20', '29', '52', '20', '39', '6A', '31', '39', '73', '41', '52',
'94', '5A', '62', '8B', '73', '7B', '94', '4A', '94', 'EE', '94', '9C', 'B4', '9C', 'C5', 'EE', 'C5', 'CD', 'CD',
'C5', 'DE', 'EE', 'E6', 'EE', 'E6', '08', '00', '00', '10', '00', '00', '10', '08', '00', '1B', '07', '00', '34',
'0F', '00', '4A', '1B', '0A', '7B', '30', '12', 'A7', '41', '1A', 'E8', '68', '2D', 'FF', 'B1', '4F', 'FF', 'F4',
'7E', 'FF', 'FF', 'B1', 'FF', 'FF', 'D5', 'FF', 'FF', 'EE', '04', '04', '04', '0B', '0B', '0B', '13', '13', '13',
'1B', '1B', '1B', '23', '23', '23', '2B', '2B', '2B', '33', '33', '33', '3B', '3B', '3B', '43', '3B', '3B', '43',
'43', '43', '4B', '43', '43', '4B', '4B', '4B', '53', '4B', '4B', '53', '53', '53', '5B', '53', '53', '5B', '5B',
'5B', '63', '5B', '5B', '6B', '63', '63', '6B', '6B', '6B', '73', '6B', '6B', '73', '73', '73', '7B', '73', '73',
'7B', '7B', '7B', '83', '73', '73', '83', '7B', '7B', '8B', '7B', '7B', '8B', '83', '7B', '8B', '8B', '8B', '97',
'97', '97', 'A7', '9F', '97', 'B7', 'AF', 'AF', '2B', '23', '23', '33', '2B', '2B', '3B', '33', '33', '43', '3B',
'33', '4B', '43', '3B', '53', '43', '43', '53', '4B', '43', '63', '4B', '4B', '5B', '53', '4B', '63', '53', '4B',
'63', '53', '53', '63', '5B', '4B', '63', '5B', '53', '6B', '5B', '53', '6B', '63', '5B', '73', '63', '5B', '73',
'63', '63', '73', '6B', '5B', '73', '6B', '63', '7B', '6B', '63', '7B', '6B', '6B', '83', '73', '63', '83', '73',
'6B', '8B', '73', '6B', '83', '7B', '6B', '8B', '7B', '73', '8B', '83', '73', '97', '83', '73', '97', '83', '7B',
'97', '8B', '7B', '97', '8B', '83', '3B', '33', '2B', '4B', '3B', '33', '5B', '4B', '3B', '5B', '53', '3B', '6B',
'5B', '4B', '6B', '63', '4B', '7B', '5B', '5B', '73', '63', '4B', '7B', '63', '53', '7B', '6B', '5B', '9F', '8B',
'6B', '23', '13', '13', '43', '3B', '23', '4B', '43', '2B', '53', '4B', '33', '63', '53', '3B', '1B', '13', '0B',
'3B', '2B', '1B', '3B', '33', '1B', '53', '2B', '1B', '43', '43', '3B', '53', '53', '4B', '5B', '5B', '53', '7B',
'7B', '73', '7B', '83', '73', '9F', '9F', '97', 'A7', 'A7', '9F', '2B', '2B', '23', '33', '33', '2B', '3B', '3B',
'33', '43', '4B', '3B', '4B', '4B', '3B', '4B', '53', '43', '5B', '5B', '4B', '63', '63', '4B', '63', '6B', '5B',
'6B', '6B', '5B', '6B', '73', '63', '43', '43', '2B', '63', '73', '4B', 'EF', 'DF', 'A7', '13', '13', '0B', '23',
'23', '13', '33', '33', '1B', '1B', '1B', '0B', 'CF', 'AF', '3B', '8B', '83', '1B', '0B', '0B', '00', '27', '27',
'00', '83', '8B', '83', 'B7', 'BF', 'B7', 'DF', 'FF', 'DF', '4B', '5B', '4B', 'BF', 'FF', 'BF', '97', 'FF', '97',
'0B', '2B', '0B', '3B', '43', '43', '4B', '53', '53', '53', '5B', '5B', '6B', '73', '73', '73', '83', '83', '7B',
'83', '83', '8B', '97', '97', '1B', '23', '23', '33', '3B', '3B', '4B', '5B', '5B', '63', '73', '73', '63', '7B',
'7B', '6B', '7B', '73', '6B', '7B', '7B', '63', '83', '83', '73', '8B', '83', '83', '97', '97', '7B', '9F', '9F',
'8B', '9F', '97', '8B', 'A7', 'A7', '53', '73', '73', '0B', '1B', '1B', 'DF', 'EF', 'FB', '43', '4B', '53', '53',
'5B', '63', '5B', '63', '6B', '63', '73', '7B', '6B', '73', '7B', '6B', '7B', '83', '6B', '7B', '8B', '73', '83',
'8B', '73', '83', '97', '7B', '8B', '97', '8B', '9F', 'A7', '97', 'AF', 'B7', 'AF', 'D7', 'F7', '7B', 'BB', 'F7',
'37', '57', 'A3', '4F', 'A3', 'F7', '29', '29', 'FF', '3B', '3B', '43', '4B', '4B', '53', '53', '53', '5B', '5B',
'5B', '63', '63', '63', '6B', '73', '73', '7B', '83', '83', '8B', '1B', '1B', '23', '23', '23', '2B', '33', '33',
'3B', '3B', '3B', '4B', '4B', '4B', '5B', '5B', '5B', '6B', '2B', '2B', '3B', '0B', '0B', '13', '0F', '0F', '2B',
'1B', '23', '53', '2B', '3B', '7B', '00', '00', '0B', '00', '00', '3B', '43', '3B', '43', '4B', '43', '4B', '5B',
'53', '5B', 'FF', 'FF', 'FF', 'FF', 'FF', 'FF'
};
Obviously, we want to avoid doing that. We can't generate the palatte since there is no way to know before hand what it should look like, the palette is required (you don't even want to see what happens when you aren't using a palette, or the wrong palette), and that means that we either encode it in the binary, require the original palette files, or dump it into a table. And remember, there is a different palette for each and every mission.
And per Selectah's suggestion of generating a 16-bit palette, that isn't an option. The nebula files just don't work that way. They were designed to function with a very specific 8-bit palette. We could possibly upgrade it to use a higher color count, but I highly doubt that it would be worth the effort involved to do something like that.