lowyhong: Thanks for all the recommendations, in particular the RPG ones. Is GURPS really that hard? Maybe I'll start with D&D 4E after all.
For board games, right now I have my sights set on, in addition to the OP's, Arkham Horror, Car Wars, Descent Journeys in the Dark. The Battletech one looks worth considering. Giant robots ftw!
Also thanks to Judas Is Carrot for the Fallout RPG. That is the one designed by Sawyer right? Skimmed through a bit of it, and it looks suitably complex. I wish there's more than one adventure though.
Of you're interested in First Edition Descent, get it now. 2nd Edition is coming out soon, and 1st Edition stuff isn't ever seeing a reprint.
As someone who has gotten in to board gaming in the past year and a half, let's see what I can come up with for suggestions...
Warhammer : Chaos in the Old World - Yes, it's a board game (not a minis game). Up to 4 players (5 with expansion), each playing as one of the demonic gods of Chaos, racing to be the first to despoil a planet. It's a great game with a lot of strategy and 4 (or 5) completely asymmetric sets of abilities : different unit numbers and skills, different card decks, different everything. It's a terrific game and you don't need to be a big WH fan to get in to it. It does REALLY need 4 players, though. You can play with 3, but then you're leaving someone out.
Survive : Escape from Atlantis - A reprint of a classic game from the 80's. It's a fun, quick little game for up to 4 (or up to 6 with a mini add-on). Each player is trying to get their islanders off the main isle and to the safety of the corners of the board before the island sinks and the volcano explodes. Lots of screwing each other over with whales, sea serpents and sharks (and giant squid with another little mini add-on). I've played this with buddies, and I've played it with the little nieces and nephew, and always have fun.
Galaxy Trucker - Up to 4 players. It's split in to three segments. The first section of each segment involves the players grabbing component tiles and trying to build their ships. It ends in hilarity and chaos. Then you actually go through your 'run' with the ships you built, encountering positives (planets to be harvested for cargo, ships to plunder) and negatives (pirate attacks, slaver attacks, war zones) from the cards you randomly shuffle together to form the decks for each segment. At the end, the one with the most money wins. It's chaotic, and it's a lot of fun.
Cosmic Encounter - Up to 5 players. Very simply game, with each player trying to be the first to get 5 colonies on the planets of the other players through battle. 50 unique alien races with unique powers, attack value cards dealt out from a common deck, tons of chaos. One caveat : this game will ONLY work if you and your friends like table banter. The game is very simple, and it thrives on negotiation, back stabbing, treachery and the like. Two expansions for it that add a lot more stuff for pretty small costs.
Earth Reborn - Crazy game for 2 people (can be played with 3-4). Simple minis combat game (all minis in box. You don't need to keep buying more) with a ton of tiles in the box from which to build the map. There are a lot of things you can do in the game, but the rules are gradually introduced as you play through the scenarios. Once they're played, you can build your own maps and play your own missions using the scenario generation system in the game. It would take me an eon to type out a description, so do yourself a favor and take a look at it. I'll happily answer any questions.
Anyway, that's a good start. :)
