In diving we think in terms of partial pressures. At sea-level, 21% of air is oxygen, and .21 is also your partial pressure of O2. In order to breath at depth, though, we need to be supplied with a higher and higher pressure of gas to fight the pressure of the surrounding environment opposing our lung expansion. At 10 meters, the pressure doubles sea-level, and you are breathing gas at twice atmospheric pressure (meaning there are twice as many O2 and Nitrogen molecules in every liter of gas).
Consequently, the partial pressure of oxygen you are breathing is doubled, to .42. This continues, until you reach a partial pressure which is incompatible with life. That danger-zone is generally considered to be between 1.4 and 1.6, so air cannot be safely breathed below about 60 meters (1.6/.21 - 1 = about 6 atmospheres). Similarly, pure O2 cannot be breathed safely below about 6 meters (1.6/1 - 1 = about .6 atmospheres).
Your description of nitrogen narcosis is correct. To dive deeper than your nitrogen narcosis limits you start replacing some of the nitrogen with helium in the gas you breathe. This works up to the limits of even the most technical recreational diving, after which you will get symptoms of something called HPNS which could mean replacing the helium itself with hydrogen.
Both helium and nitrogen will get stored in your inert tissues and will bubble out catastrophically if you ascend too quickly. With either inert gas you must carefully plan your ascent to avoid the bends.