It's not a bridge, but if you wish to consider the depth of marine structures generally, a good example is the Troll A platform in the North Sea. From Wikipedia:
"The Troll A platform has an overall height of 472 metres (1,549 ft), weighs 683,600 tons (1.2 million tons with ballast) and has the distinction of being the tallest and heaviest structure ever moved by mankind. The platform stands on the sea floor 303 metres (994 feet) below the surface of the sea ..."
As a starting point for bridges you have a list of the highest bridges with the highest bridge being the Duge Bridge in China with a deck height of 565m:
As for marine crossings, there is a bridge (that apparently exceeds San Francisco Oakland Bay Bridge you have referenced) that has received instruction to proceed during 2010 but has since been put on hold. The Bridge of the Horns is a Red Sea crossing at the Island of Perim (300m sea depth) from Yemen to Djibouti that is described by COWI DK:
"The length and navigational clearance required west of Perim will likely mean at least 10km of multi-span suspension bridge, with the remainder being approach bridges. The concrete pylons will have to be supported up to depths of 300m and at the same time tower 400m over the water's surface to support the ultra-long span suspension bridge. Each pylon will be 700m. It will be enormous."
Just for information, Professor TY Lin has proposed a Gibraltar crossing that would have a height of 910m. I could not find specific information on depth, but one would assume that it would exceed 300m (the sea depth there ranges between 300 and 900m). A tunnel was originally considered but has been dismissed as it would be 900m deep, the deepest tunnel in the world is the Eiksund Tunnel at 287m.
Coming back to the underlying purpose of your question; ie Boris Johnson's proposal, I have pointed out these extreme data points to illustrate that the project is well within the bounds of current engineering capability. In my view the most significant challenge of the project would be determining the location and magnitude of the main span required so as not to interfere with shipping vessels as this would likely determine the size of piers and depth of foundations.
(Note that these depths are referenced to the sea bed, they do not include depths that might be required for foundations. Checking the bathymetric survey data at the San Francisco Oakland Bay Bridge crossing does not support a sea bed depth of 74m (looks to be in the range of 20 to 30m), therefore the depth you have quoted (74m) may include foundations; for comparison purposes the bathymetric data at the Strait of Dover yields a sea bed depth of about 50m - as you have indicated an extreme of 68m to the sea bed.)