There was a game a bit like Duke Nukem 3D (it may have come out a bit before) I remember playing on PC. All I remember is it may have been set in the future and the walls were a grayish-blue. It was first-person and there were doors that slid up in the levels.

Anyone know what it is?

Doom? Descent?

That's very vague, if you can remember anything extra, it could be helpful. Most of the FPS games before the BUILD engine had DOOM doors (that slide up) and a visual style that sounds like generic scifi doesn't really help either.

Maybe you are talking about this one?

http://www.gog.com/gamecard/blake_stone_aliens_of_gold

It might be that one but still any other suggestions would be appreciated.

Blood

Descent, Quake, Wolfenstein 3D, Star Wars: Dark Forces, and Shadow Warrior.

Am I doing it wrong?

Quest for Al-Qa'eda: The Hunt for Bin Laden
It is a total ripoff, but it`s a lot like it

Shadow Warrior
One unit whole blood (Blood)
Wolfenstein 3D

Duke Nukem 3D was made in the build engine
Redneck Rampage maybe used the Duke3D Build Engine

While we're at it:
List of Wolfenstein Engine games

and
List of Doom Engine games

This thread is hilarious.