For the console itself - don't even think about the Core or the new Arcade versions. Neither has the hard drive. Out of the rest (premium, Halo 3, or Elite), it really depends on color choice and hard drive size - all of them are shipping with HDMI ports. The Halo 3 edition is essentially a premium with a really great paintjob...if he likes Halo 3 that much, then it's probably worth the extra $50...but it does include the matching Play & Charge kit. The Elite gives you the 120GB HDD, which is nice if you plan on buying movies and such through Live.
All of them should come with the basic wired headset, so that should be covered. If you can run Ethernet to the console, I'd recommend that over wireless (it's cheaper and more reliable). But a second controller is a nice thing to have. I'd also recommend the
Play & Charge kit if you don't get the Halo 3 edition.