That's not really true. You can decode N-bits in one step, for example, via 2^N N-bit compares. For small N, that's totally doable.
I like examples: 74AHC00 2-input gate has typ 4.5ns propagation delay at 25˚C/15pF/3-3.6v http://www.nxp.com/documents/data_sheet/74AHC_AHCT00.pdf
74AHC30 8-input gate has typ 5.0ns propagation delay at 25˚C/15pF/3-3.6v http://www.nxp.com/documents/data_sheet/74AHC_AHCT30.pdf