We present the first results from our NASA Keck Observatory Database of Ionized Absorbers toward Quasars (KODIAQ) survey which aims to characterize the properties of the highly ionized gas of galaxies and their circumgalactic medium (CGM) at 2<z<4. We select absorbers optically thick at the Lyman limit ({tau}_LL_>1, logN_HI_>17.3}) as probes of these galaxies and their CGM where both transitions of the O VI doublet have little contamination from the Ly{alpha}, {beta} forests. We found 20 absorbers that satisfy these rules: 7 Lyman limit systems (LLSs), 8 super-LLSs (SLLSs) and 5 damped Ly{alpha} (DLAs). The O VI detection rate is 100% for the DLAs, 71% for the LLSs, and 63% for the SLLSs. When O VI is detected, log(N_O VI_)=14.9+/-0.3, an average O VI column density substantially larger and with a smaller dispersion than found in blind O VI surveys at similar redshifts. Strong O VI absorption is therefore nearly ubiquitous in the CGM of z~2-3 galaxies. The total velocity widths of the O VI profiles are also large (200<={Delta}_{upsilon}_O VI_<=400 km/s). These properties are quite similar to those seen for O VI in low-z star-forming galaxies, and therefore we hypothesize that these strong CGM O VI absorbers (with {tau}_LL_>1) at 2<z<~3.5 also probe outflows of star-forming galaxies. The LLSs and SLLSs with no O VI absorption have properties consistent with those seen in cosmological simulations tracing cold streams feeding galaxies. When the highly ionized (Si IV and O VI) gas is taken into account, we determine that the {tau}_LL_>1 absorbers could contain as much as 3%-14% of the cosmic baryon budget at z~2-3, only second to the Ly{alpha} forest. We conservatively show that 5%-20% of the metals ever produced at z~2-3 are in form of highly ionized metals ejected in the CGM of galaxies.