Having recently (legally!) downloaded Allegiance, Hidden & Dangerous, and a few other games that were either free to begin with or released commercially and subsequently distributed for free by their developers. In that spirit, I wanted to check and see what other independent or abandoned games I might be missing out on? I’m not picky, so I’ll try anything that people recommend at least once.
Not a specific recommendation, but you should look at Home of the Underdogs, a great source for abandonware games. They’ve got hundreds or thousands of old games that are no longer being sold, and while the legality is borderline, they do respond to cease-and-desist orders, so anyone paying attention to the copyrights they hold isn’t being hurt by it.
Specifically, you should try Zork, the classic text-based RPG. You’ll never really understand the fear of the grue until you do!
Ooh, that is exactly the sort of thing I was looking for… thanks for the link!
Home of the Underdogs has been dead for a while, sadly. It was one of my favourite websites, too 
I suppose you can still browse the website and get the games elsewhere, though.
It’s not really in the same vein as the games you mentioned, but I’m going to go with the standard freeware pimpage of Cave Story.
I was going to suggest Allegiance, but I’m happy you discovered it yourself. I don’t have any specific recommendations either but here is a list of 100 (er, 99) of the best legal full version games you can download online: Link
Rockstar has released GTA1 and GTA2 as freeware by the way.
Star Control II has been released as freeware, under the name “The Ur-Quan Masters”. It’s a 2d one-on-one space combat game that’s been grafted into an exploration-style RPG. I love it to pieces. (Note that for the RPG part you definitely do need to either keep a notebook or download spoilers from somewhere if you’re used to newer games that keep track of eg. coordinates of important star systems in-game).
Tribes, Tribes, Tribes, Tribes! Tribes! And Progress Quest.
Abandonia Is a good site to find old games, i prefer it to underdogs. Here you can find one of my favorite RPGs of all time, Betrayal at Krondor.
Command & conquer red alert is also freeware these days.
One of my favorite oldies is called Darklands - an open-ended RPG set in medieval Germany, with quests and story threads in many of the cities actually around at the time. At night, you can hunt for bandits and earn renown, while during the day you can shop, pray at the Church, train your skills, or explore the countryside.
Or if you’re looking for more futuristic fun, you can buy classics like Fallout 1 and 2 at Good Old Games.