I think Postal 2 sticks to this aswell. The city map is, well, there. Each following day an extra piece of the town is unlocked and you can walk around in a bigger map.

But, the maps are still the same, as the week progress. You gain new weapons, have to complete new missions and there is more police on the streets.

Toolmaker

Freelancer is not an FPS but the game mechanics are the (sort of) same. As Wavinator correctly (as usual) said, the fun of getting from point A to point B in GTA and the others is slaughering grannies, knocking out other vehicles (especially motercycles) and generally being a nuicence. The reason I mention Freelancer is that the aim in singleplayer is to advance the storyline, and the aim in multiplayer is to get those extra credits to buy the next ship/weapon. And Freelancer was still fun.

I have had a concept for a game in my head for a while, it is kind of similar to Deus Ex in the way you have a base and get quests from there. After that you can choose how you want to do the mission, and how you do it, and in what order effects the outcome of the story.

Having a seamless FPS world could be fun, but it would need some serious designing to make it so.

A virtual cityscape like that of Deus Ex 2's Upper Seattle would make a great FPS.

On a side topic:
That game had so many great points about it. A combination of FPS and RPG, it was awesome hunting around for those little canisters. That and I want to be an Omar Protector. Or Alex D. I've gotten hooked on the kidneythieves music (N.G. Resonance).

So ++ to anyone with a DeusEx/GTA/Halo hybrid in dev.