Kaos36: Another World was the first game i played on pc, and a side scrolling shooter called mansion or something where you ran through houses with a shotty blasting zombies. First FPS games were Duke nukem and Quake which both came out the same time or few months apart. One game that got me glued to the monitor was 'Aces of the Deep' Where you commanded a German U-boat in the Atlantic during World War II sinking british shipping. Was fantastic as the campaign was dynamic meaning each time you went on patrol it was different. I played that game for about 2 yrs.
The game you were thinking of is Dangerous dave 2.. i posted it in the 2nd page of this thread