The basic formula for a First Person Puzzler is as follows:
Unique Ability + Maze = Win.
If you want examples of this, there is of course Potal:
Portal Gun + Maze = Win.
Or if you want further proof, there's always Mirror's Edge:
Professional Level Ability to Run and Jump + Maze = Win.
Sure, there are probably a lot of people out there who don't enjoy Mirror's Edge, but speaking as a Post-Op on some foot surgery, the game's a lot of fun when running is a challenge ;P
This being said, you basically need to come up with a compelling story for why the person needs to get through said maze. In Mirror's Edge, it was the cops constantly on your tail monitoring your every move. In Portal, it was the simplistic, but expertly pulled off role of a lab test subject which you were forced to assume.
I can't recall the name of the game, but I think the LA Disaster game after a giant earth quake, where you have to make your way through the city, would work well. A disaster in general works well in my opinion. An accident like Black Mesa would be fun to navigate through, albeit without the aliens. Or at least no alien encounters.
Now that I've been rambling for a bit, the first person puzzler I would like to see is one featuring a shape shifter. Similar to the last generation platformer Dr. Muto, it would be interesting if the first person character had a collection of forms, which would work for different situations. A wolf form for speed, a mouse form for getting through tight spaces, etc.
A plot for the game wouldn't be too hard to come up with. To take a page from Legendary or Prince of Persia, the hero could say, open pandora's box, (or a similar concept), unleashing all sorts of beasts and creatures into the world. Being the one who opened the box, he could take the form of all of these creatures wreaking havoc, and it would be his job to retrieve the box and seal them all back inside. (Twist Ending: If you don't change back to human in the last scene you get trapped too ;P).
Well, there's my two or three cents.