We present an improved analysis of halo substructure traced by RR Lyrae stars in the SDSS stripe 82 region. With the addition of SDSS-II data, a revised selection method based on new ugriz light curve templates results in a sample of 483 RR Lyrae stars that is essentially free of contamination. The main result from our first study persists: the spatial distribution of halo stars at galactocentric distances 5--100 kpc is highly inhomogeneous. At least 20% of halo stars within 30 kpc from the Galactic center can be statistically associated with substructure. We present strong direct evidence, based on both RR Lyrae stars and main sequence stars, that the halo stellar number density profile significantly steepens beyond a Galactocentric distance of ~30 kpc, and a larger fraction of the stars are associated with substructure. By using a novel method that simultaneously combines data for RR Lyrae and main sequence stars, and using photometric metallicity estimates for main sequence stars derived from deep co-added u-band data, we measure the metallicity of the Sagittarius dSph tidal stream (trailing arm) towards R.A.2h-3h and Dec~0 deg to be 0.3 dex higher ([Fe/H]=-1.2) than that of surrounding halo field stars. Together with a similar result for another major halo substructure, the Monoceros stream, these results support theoretical predictions that an early forming, smooth inner halo, is metal poor compared to high surface brightness material that have been accreted onto a later-forming outer halo. The mean metallicity of stars in the outer halo that are not associated with detectable clumps may still be more metal-poor than the bulk of inner-halo stars, as has been argued from other data sets.