There were a couple shareware games that had such good stories I had to buy the full versions. Solar Winds -- You play as a bounty hunter who exposes what appears to be a galactic conspiracy, only to learn it's something much deeper than that. Traffic Department 2192 -- Kind of Dune-inspired top-down shooter, with quite a good story. I will say that the endings to both games were a bit lackluster, but the overall experience was definitely worthwhile.
I remember both of those games. I only played the demos, but the plots were exceptional. As for plots, I'd also recommend the shareware Exile Trilogy (a traditional party-based turn based RPG) - later remade as Avernum. It had a nice story too.
Solar Winds was fantastic. It's too bad I could never beat it. I kept getting stuck near a black hole after your first return trip with the Hyper Drive. I never knew what to do.
One issue with that game is that you really had to follow the script, or you were screwed--the game would "forget" your next objective and if you ran out of fuel, you were toast. And also, if you flew past the invisible "galactic barrier" you just plain blew up, with no warning. Were you stuck because you ran out of fuel or what?
^ Well, we're going going back over a decade here. Let's see what I can remember. I remember getting the hyperdrive fuel to go to the distant solar system/galaxy (although I dumped all the fuel into my stats and spent an hour or so getting there with the normal engines. I was godly powerful) and meeting an alien ship that tells you to leave. I go back to the starting system (a few hours later) and get a new mission. I was to go arrest a guy (scientist?) near a black hole. When I get there I can go through the black hole with him (and die), destroy his ship, or ignore him. No matter which option I chose I couldn't figure out what to do next.
You have to transport the tricillium just before you go into the vortex. Otherwise, your ship will blow up! So, you transport it, then go through the vortex with the scientist.