IMHO, one things that makes a good 3D game is scenery. Call it blindingly obvious, but any 3D game without scenery might as well be Wolfenstein (or even 3D Monster Maze, and that's sooo 1980's). To this end, I've just added some signs to the map that the player starts on, to make it more homely and, err - I can't think of the word. Realistic? Maybe, but it's set in the future anyway, so realism isn't exactly top of the agenda. More natural? Easier to navigate around? I dunno, I give up.
I've almost done the first "episode" of this game that I've christened Last Remaining, and as soon as Sourceforge get off their *rses and accept my project, the sooner the proles can play it and hopefully give me some feedback. It's far from complete (what comes before alpha?) but has the makings of a could-be-good game.