Thanks DP.
Yes, that Rebel shot was actually ISO800. THe thing is, the ISO1600 shots were so clean, I wasn't sure which it was until I looked at the EXIF.
Your picture is normal for an underexposed shot. Once you try to compensate in software, it will definately be noisy.
Try your best to get that histogram as far "to the right" as possible without clipping the highlights.

