Combinations to Avoid for Early Games?

Rats and vats (nickname for Pike Industrial Complex) is normally a fairly tame environment, but yeah, it does pair badly with Omnitron.  I'd probably avoid Rook City and Wagner Mars Base for now.  I'd also probably avoid The Chairman, The Matriarch, Apostate, and Citizen Dawn as they are all harder villains.  On the hero side, Wraith, Expatriette, Fanatic, and Tempest are all relatively straightforward heroes that have good ways to deal with Ongoings or Environments that are troublesome.  Visionary and Tachyon are slightly less straightforward heroes that also have good ways to deal with Ongoings and Environments.  I'd avoid Absolute Zero, Argent Adept, Unity, and Nightmist for your first game or 2, but in all fairness, Argent Adept is my favorite hero; he's just not "simple".

The Ennead on hard mode is NOT recommended. (or anything, for new players)

Honestly, though, any combination is fine. My first few games the people I was playing with (one vet, mostly new) forced me to play each villain and environment once each. (this was before Rook City.) We may have lost a game or 2, but who cares? The point is that you enjoy yourself.

Honestly I could always play in Megalopolis since it is just the perfect generic superhero throwdown enviroment.

I agree that the Pike Industrial Complex can be tough... I was there recently vs Spite and it felt like the perfect enviroment for him... but also very painful for us.

I have said this before but Rook City + anyone with minions (Chairman, Voss, Matriarch) is hellish.

Lastly I cannot suggest the Ennead enough, most interesting design yet. I fought them in the Realm of Discord and it was a great experience... just tough enough although Nightmist kept them from drawing cards a few times making victory possible.

I find Megalopolis to be terribly unforgiving with all of its "Heroes cannot _______ this turn" cards.  Insula Primalis and Wagner Mars Base have always been good for my group.

I would stick to the core set for a while and work your way up to the expansions over time.  Pretty much ALL of the Rook City villains can be rather harsh unless you build a team to take them on.  Gloomweaver is a lot of fun and my group has never had too much trouble with him.  The other Infernal Relics big bads are pretty rough, though.  As far as heroes go I would avoid Zero, Adept, and Nightmist.  The other heroes are pretty straightforward (just understand that Visionary is a support character with massive utility for the team and you'll be ok).  My suggestion is to focus on the Core and only splash a few of the other sets cards into games here and there.  Each set gets gradually more detailed in its execution.

I played as Wraith for my first several games, before I actually owned the game myself. Then, once I got hold of the Enhanced Edition, Rook City, and Infernal Relics a few weeks ago, I tried playing as other heroes. We've (two of us) played in every environment multiple times, and fought every villain at least twice. I think there's actually a couple of heroes I haven't played as yet, but I've tried most of them now.

Personally, I think Nightmist is epic. I suppose she can seem complicated at first but really, within the first turn I figured out the basics and so far I've never lost a game when I've played her. Ever. And I've played this thing a lot now :D. She works a bit differently to other heroes due to the number-value thingy on her cards and the fact she basically uses her hitpoints (and cards) as currency to make stuff happen, but she's epic just 'cause she's so good at healing herself (actually so is Ab' Zero - as mentioned he is quite complicated but as long as you can follow the whilte Fire/Cold thing he's great :)). And she has really good deck control - she has a card called Mistbound which she can play on another deck to stop any cards being drawn from that deck until the start of her next turn. Is this card useful? Pff, have a guess ;). Aaww, Matriarch, can you not summon any birdies this turn because I put MIstbound on your deck? Aaww, diddums...now you just wait til next turn when I'll play my other Mistbound card, and hopefully by the turn after that I'll have got the other one back into my hand again :D.

The thing with Nightmist is that you want to draw a lot of your deck, but try not to quite draw all of it. As I found out at the weekend when did just that for the first time, a lot of her cards require you to reveal cards from the top of your deck - can't do that if they're all in your hand ;). Fortunately, she has several cards which require you to discard stuff, so you can get a "storage" deck back again :).

Oh yeah, and she can also, with the use of a certain equipment card, discard cards to redirect damage once per turn (the first time she would take damage in that turn). Omnitron's electro-thingy comes out and tries to hit her? Discard two cards, redirect its damage back to itself - fzzt, all gone! :D

Anyway, Nightmist raving aside...Wraith is good. Legacy too. The two of us played Legacy and Ra and we totally kicked the Matriarch's arse, and she can be difficult due to her many many birdies :D. Ab' Zero is also very effective if you get the right cards out but he is possibly the most complex character to play. Also, if he's playing with Ra, don't let Ra put out Imbued Fire (though pretty much anything else is fine as long as it doesn't affect Ab' Zero's damage type, or damage received if Cold or Fire) because that'll mess him up. If Ab' Zero has the right cards out, getting Ra to nuke him with Fire is actually a good idea, 'cause he can end up healing off it, or redirect it to something else :). You want someone else present who has deck control, though, if you're fighting someone such as Omnitron who can destroy equipment. Ab' Zero doesn't like having his stuff destroyed!

Regarding which villains to face/environments to fight in, I would suggest that if you're facing someone for the first time, make sure you've got someone on your team who has deck control capabilities. Wraith is fantastic at this, with her Infra-Red Eyepiece. Not only does she get to draw a free card when she uses it, if she has her Utility Belt out she can still use another power after she's looted the top of a deck to see what's coming up :). Visionary is also good at this (controlling stuff is her speciality - she's not DPS, she's Crowd Control ;)), as is Nightmist (but I think I covered her pretty well ;)).

Maybe play around with different combinations and see what works best. Chances are you'll find yourself playing as a certain hero and going "Oh wow, I love this hero, they're so fantastic, I feel like I can do anything with them". Of course, some heroes get their arses handed to them on a plate by some villains/environments, and in some cases you can be facing someone whose arse you've kicked multuple times and have them play a really horrible card just at the wrong moment which destroys all your stuff, or maybe the environment brings out some nasty hard-hitting creature that just messes with your plans. I suppose, what with the number of possible combinations of heroes/villain/environment, we could talk about them for a long time. Some heroes work well against certain villains but get their arses kicked by others (or by the environment). Some are good all the time. Don't forget interactions with other heroes - as mentioned, Ra can boost Ab' Zero nicely, but that's not the only combo that can work well. Legacy and pretty much any damage-dealer is good. Ra, of course. Or Fanatic - because of the way her cards tend to deal small amounts of damage, even a +1 damage can give her a huge boost. For example, her base power is one point of Radiant damage and one point of erm...something else damage. Give that a +1 from Legacy and it becomes two damage and two damage (so, four damage). If you were playing in, say, Insula Primalis and had an Obsidian Field come out, that's another +1 damage, making the total damage for her innate power six damage! And if Ra turned on Imbued Fire making it two hits of Fire damage, again with a +1, that's eight damage...you can see where this is going ;).

Mind you, heroes such as Wraith, Bunker, and Haka all have ways to do plenty more damage than that in a single hit if they put enough power into it. It costs you a lot of cards to do so but it's not something you'll probably do partway through the game (unless it's to kill Baron Blade's first phase, I suppose). Satisfying to end the game with, though, if you can do tens of damage in a single hit :). I'd say even more satisfying is redirecting someone's damage into their own face and finishing them off, though. That's always good >:).