Mirror's Edge is extremely linear - there's usually exactly one right way to do things, and if you don't do it that way, you die, rinse, repeat, ad infinitum, ad tedium. I couldn't play it for more than a couple of hours.
Two games I relate to on the theme of navigation of space are the Thief series, and Far Cry 2.
With Thief, you have a rough map, and your task is to navigate the territory to get to your goals, avoiding hazards such as loud tile and metal, bright lights, guards, traps etc. With a selection of arrows for making the ground silent, extinguishing torches, and rope arrows for climbing, it can be a lot of fun. Constantine's Mansion (Constantine's Sword mission) is a particularly architectural delight, with optical illusions and a network of grassy tunnels joining different floors.
Actually, a defining metaphor of the first two Thief games is architecture as sexuality; in the first, your enemy is the earthy Pagan Trickster and his co-conspirator, wood nymph Viktoria, and you pursue him into the bowels of the earth. In the second, your enemy is a technocratic religious self-described prophet, and you pursue him in a monstrous skyscraper of metal, working your way up and up.
Similarly, a substantial and (for me at least) entertaining part of Far Cry 2 relates to the navigation between mission objectives. The roads are patrolled, and intersections are heavily enough guarded that clearing them risks depleting ammo, so the best policy is generally to navigate in the gaps between the roads, choosing crossing points, swimming in rivers, selecting the right angle of entry approach for mission destinations, etc. Given that every main mission involves at least three different destinations (one to your buddy in a safehouse, one to the buddy's preferred mission target, and a third as the original mission), you need to enjoy this navigation to get the most out of the game. (Most people didn't; it seems they stuck to the roads and found the guard checkpoints tedious.)
As to games like Half-Life and its successors in particular, they seem to me to inhibit exploration and be very linear. Any time there's an interesting passage hidden away in a corner, I make a note of it and scout out ahead to see what the mainstream alternative is; but in HL2 and episodes, it usually turns out that the main branch is a dead end, and you must go back and investigate that hidden passage. So it kills any chance of you feeling clever, and makes the unorthodox mundane.