The first level was the best one of the whole game because you had so many options to reach your goal. It's sad that level design went on a continuous plunge from that point on. Even Deus Ex HR was pitifully limited and with tiny linear levels in comparison. The level of brilliance in the original Deux Ex will never come close to being topped.
I think part of why it worked is that many of the guys who designed these games used to work on pen and paper RPGs that put a lot of emphasis on creative solutions and different approaches. Warren Spector used to work at Steve Jackson games before becoming a game designer. The young kids nowadays have grown playing mobile and Facebook games and lack the experiences the older generation of gamers had.