Elite was impressive. The whole "universe as a random seed number" thing. Some years later I was impressed by Frontier, the sequel, where you had seamless takeoff from planets into space, no transitions or loading screens... this was very impressive back then, in a way gamers today possibly cannot understand.

I also remember Swashbuckler! Another recommendation for OP.