Psychonauts for sure. It's a classic.
I'll lobby for RezHD, as it's my current addition; at least check out the free demo and see if it's for you. It's stupid-fun if you already have a hi-def display and surround sound, and it's $10.
You already have Halo 3, so peek around at the Forge-ed maps folks have made. Especially keep an eye on the Favorites [http://www.bungie.net/Online/BungieFavorites.aspx] hand-picked by Bungie staff from the community; if you've linked your gamertag to Bungie.net, you can even pick maps/films/games from the web site and automagically have the variant pushed to your Xbox the next time you fire up Halo 3. You may or may not want the current map pack, but if you do be advised it'll likely be available for free soon. And online co-op rawks if you throw in some skull modifiers to keep it challenging.
You may want to have a look at Gears of War if you haven't already; it's had some serious staying power on Live's "top 10" played list. (Hasn't it had a price cut already, too?) And it has online co-op too.
I haven't played CoD4 multiplayer yet, but it is rivalling Halo 3 for most-played so it's likely worth checking out. (Me, well, I've kinda dropped off the multiplayer lately; too busy Achievement-grinding and trying to relearn how to not suck.)
-- Steve