I completely agree on the first five paragraphs. Well written. I have yet to see a game as good as the first Deus Ex. Do you have any suggestions besides the usual?
The first Crysis had some good things in terms of freedom of movement and tactical options. I'm told Far Cry 2 is pretty good in this regard as well.
Otherwise, the original Operation Flashpoint/ARMA are pretty much the ultimate FPS sandbox. As long as you are ready to eat bugs and suffer the terrible physics. Completely different from Deus Ex, obviously, but definitely not on rails.
