I would like to add Midwinter ('89) to the list of old FPS engines, after all it did have huge fractal landscape and freedom of movement.
Midwinter.. I got a really big "The Sentinel" feelling about it. I remember playing Flames of Freedom and feeling it really related to that classic.
So, yes 1986's the Sentinel created a true 3D environment where the player could (walk/)Look around and as such is half a decade earlier than other FPS attempts.
I played it on C64