Hey, I can contribute here! I just finished my game room at the start of the year, and have a 6 pc setup for weekly LAN stuff. Here's what I've found as hits and misses by genre.
RTS - Any real time strategy games are risky, just because you always end up with one person who is good enough to take on 2-3 others alone. After a while it ended up that we would have to play teams, trying to balance that out as much as possible. Even then, its not a whole lot of fun when 4 of you lose to the 2 man team. Generally we don't play RTS anymore, unless it ends up that everyone is equally terrible.
Build games - Games like Terraria and Minecraft are also usually a miss. You end up with a few people who are really into it, and a few people who just aren't, which equals boredom and going home early. IT's also really hard to not just go off and do your own thing in those kind of games, so eventually you end up with a couple people working together, and the rest all just off doing their own thing. At that point, why are you having a LAN party?
Turn based - You mentioned playing Heroes 3. I had the same idea. PARTY KILLER. Heroes can be a lot of fun with 2-3 people sure, but any more than that and you are often waiting 15 minutes+ for your next turn. Emphasis on the +. Often, by the time a player gets his next turn, he has forgotten what exactly he was even doing, which slows things down further. I even had the bright idea that we would do kind of a multiple game setup, so we would all be swapping in and out of another game while running over and hotseating a game of heroes. All that did was make people groan when they had to go take their turn. Great games, just no fun at a LAN party.
FPS - You pretty much can't go wrong with anything here. I'm not that big into FPS games myself, but with a group of people, you can't help but have fun. I've found a lot of younger\older players have a lot more fun with a slower paced FPS (tactical FPS?) than with a fast paced game like Quake or UT. Well, they still have fun with those, but tend to come in last place every game. I bought a bunch of copies of Far Cry 2 for the PC's and people love that. Seems like anyone can win a match at that, even people who generally never play games, lots of fun. Ohh and Borderlands if you only have 4 people. That tends to be the default for 4 at my house since BL2 came out.
RPG/Adventure - Most people seem to like these as well. Dungeon defenders, Torchlight 2, Diablo 3 have all gone over well. I personally feel like they are not AS good at fostering a great time as some of the FPS's, as everyone is working together, but again, just kind of doing your own thing. The most exciting thing that can happen is basically "Is this +10 cool mace good for you?" - "Yeah man, that's a huge upgrade!" - "Here you go." - "Thanks.". You never have anyone screaming or laughing their head off, but everyone does have a good time.
Simulation - I bought 6 copies of one of the need for speed games. I've never been able to talk anyone into playing. No one wants to race around in my house for some reason. Sounded fun to me!
OVERALL, I would say that you are a lot safer with any game that lets your group play together (as much as I hate to say that, as that's not my preference), because either you all lose and everyone has fun, or you all win and everyone has fun. No one likes losing at everything all night. They don't leave happy, and tend to leave early if that's the case. FPS games are almost always a safe bet, but you might want to switch the style up a couple times to make sure everyone's having a good time (Do an hour of capture the flag, an hour of deathmatch, an hour of humans on a team vs increasing difficulty waves, an hour of a slower fps, etc). You can probably throw in a couple RTS matches in there as well, but I guarentee after a couple of games, the people not doing well will want to go back to FPS or whatever. RPG games tend to be an all night type of thing, expect to play only that game for 5 hours once you turn it on. In the end, its hard NOT to have fun at a LAN party. Do your best to manage it, suggest changing games if you feel like someones not enjoying what you guys are playing, let people take breaks pretty often, just watch your party and try to be a good host is the main thing.
Lastly, if you think you might want to do this regularly, watch Steam at the big sales, the summer sale is mainly what I look for. Wait for a game to be $3-$5 and buy 1 or 2 4 packs. Set up 4-8 steam accounts for yourself (lanparty1, lanparty2, etc) and give them all a generic password. Gift all the extra copies to them. It's still really cheap and a solid way to make sure everyone can play. A ton of games are just more trouble than they are worth to pirate anymore. You will find accounts 1-4 will have most of your games ( no reason to buy 8 copies of Left for Dead 2 when you can only play 4 player, etc), with a few games ending up in overflow. Also watch for humble bundles. 5 games for each of your extra accounts at $1 per account? Yes please.
Hope that helps!