"Hydrophobia: Prophesy" reminded me of Uncharted. It's an environmental puzzle solving game with some combat. In many ways, it's not put together as well as Uncharted but it's worth the $5 or whatever on Steam. You might check it out.
How about, where it really, really, REALLY started? Prince of Persia. The 2008 version is pretty awesome.
Tomb raider was were it started. The first PoP games were sidescrollers and in no way "like Uncharted". PoP did not switch to 3D until 1999, 3 years after the original Tomb raider.