Tried the demo of Trra Nova back in the day, and it didn't grab me. But everyone raved about it. Maybe if was one of those games ill served by their demo.
from the demo alone, it seemed too open - all outdoor environments and hills, rather than actual "levels". Of course those kind of environments are fun too, but more in the mould of something like Daggerfall or Mechwarror. Fun, but a different kind of fun from an FPSey exploring. (but maybe it changed after the demo level).
Future shock was mostly open levels (hollywood hills, LA) but, it was closer to a traditional FPS in terms of design. When you entered buildings it was a standard FPS, but outside was a little closer to daggerfall cities (if they were hand crafted not random).

You're directed by waypoints at all times. So it's not like you're running around lost. But yes, it stays with outdoors environments in the game.

While I agree that finding your way can be fun, I also think that there's a good reason why it's more linear now. In older games I would get stuck in a level for an hour trying to find where the exit was, and that was no fun at all.

I can't remember ever getting stuck in an FPS for very long. Even back in the days of doom. Maybe in wolfenstien, but that was cos everything looked the same!
Oh wait, i did get stuck trying to work out how to get into the big tower in Jedi Knight, where you had to ride up on the top of the big door. But that was also one of my favorite parts.
But I don't really remember even the most open FPS games being that hard to navigate. Lots of other genres I'd get stuck on, but never really FPS.