Supermassive black hole (BH) mergers produce powerful gravitational wave (GW) emission. Asymmetry in this emission imparts a recoil kick to the merged BH, which can eject the BH from its host galaxy altogether. Recoiling BHs could be observed as offset active galactic nuclei (AGN). Several candidates have been identified, but systematic searches have been hampered by large uncertainties regarding their observability. By extracting merging BHs and host galaxy properties from the Illustris cosmological simulations, we have developed a comprehensive model for recoiling AGN. Here, for the first time, we model the effects of BH spin alignment and recoil dynamics based on the gas-richness of host galaxies. We predict that if BH spins are not highly aligned, seeing-limited observations could resolve offset AGN, making them promising targets for all-sky surveys. For randomly-oriented spins, less than about 10 spatially-offset AGN may be detectable in HST-COSMOS, and > 10^3 could be found with Pan-STARRS, LSST, Euclid, and WFIRST. Nearly a thousand velocity-offset AGN are predicted within the SDSS footprint; the rarity of large broad-line offsets among SDSS quasars is likely due in part to selection effects but suggests that spin alignment plays a role in suppressing recoils. Nonetheless, in our most physically motivated model where alignment occurs only in gas-rich mergers, hundreds of offset AGN should be found in all-sky surveys. Our findings strongly motivate a dedicated search for recoiling AGN.