Hey there, welcome to the forum :).
For a first game, I shall join all those who said to fight Baron Blade in Insula Primalis, with Legacy and any of Ra, Wraith, Tempest, and the other straightforward heroes who were mentioned :).
In terms of which expansion to get, they all have replayability - every deck does, I would say. That's how come we've all been playing it for so long…well, that plus it's co-operativeness. I'm not even particularly intereted in superheroes :D.
Rook City is probably the hardest in terms of villains and environments. All the villains are varying types of brutal (though one or two can become relative pushovers if you bring certain heroes against them). Of the two environments, one is generally considered the harshest upon the heroes out of all environments in the game, while the other has some annoyances and can be painful but on the whole I would say isn't nearly as bad (especially if you have environment destruction). The heroes are a martial artist mechanic guy and a woman who uses many many guns.
Infernal Relics is my favourite out of all the expansions, possibly because of the magic theme but also partially because the decks are just cool anyway. The villains are generally not too bad (although the Ennead, a group of nine Egyptian-gods-who-used-to-be-archaeologists, like Ra, are reportedly one of the most difficult fights in the game if you play them on Advanced). The environments are similarly so and I find quite interesting. The two heroes are rather toward the more complicated side of things, one in particular but he also happens to be my favourite in the game - he's kind of like a DnD (or EQ) Bard, using music and song to support his teammates and let them do All of the Things. The other hero is an occultist investigator who investigated a bit too much occult and is partly made of mist - she summons relics and casts spells and involves a lot of self-harm and self-healing to do a wide variety of stuff.
Shattered Timelines is probably my second-favourite expansion. The villains tend to vary between not-too-bad and omg-that-was-a-massacre depending on card luck, and one in particular is probably about hte toughest in the game. Certainly games against hium are unlikely to last longer than about fifteen minutes, whether you win or not (and generally speaking, you probably won't because he really hurts). The environments aren't too bad. The heroes are two that I really enjoy playing - a time-travelling cowboy sheriff guy who, once he gets set up with a few cards (which he can do within a couple of turns if he gets luck yon the draw) is epic at focusing down single targets, even without external damage buffs. The other is a diferent kind of time-traveller, a future version of Omnitron who installed an empathy drive into himself to try and understand how the various heroes help each other in order to keep defeating him (so he can in turn defeat them) and promptly realised "oh crap, I've murdered so many innocent people…this must never happen", then time-travelled back to try and destroy the first incarnation of himself. Anyway, his cards are basically heroic (and therefore somewhat toned-down) versions of the villain Omnitron's cards, and I find him pretty versatile and pretty good fun :).
What's next…oh yeah, Vengeance…that one changes things up a bit in terms of villains. Instead of getting four individual new villain decks, there are five…but they're all a team. Fed up of getting his arsed repeatedly kicked by the Freedom Five (and others), Baron Blade has put together his own team, the Vengeance Five, to try and get…well, vengeance ;). Each of the five is nemesis to one of the Freedom Five and has other nemeses (to other heroes) within their decks. You don't necessarily fight all five of these guys at once, though - when you set up a game, you fight H of them. So you'll only fight against all five decks if you have five heroes present. Then play alternates between villains and heroes (and the environment on the end, as usual). The heroes in this expansion are a good mix, I think. My probably-second-or-third favourite is in this deck, a guy who can shapeshift into any of three different African animals which provide him with different effects. There's also an archer, a Scottish lady who stabs things with energy blades, a team of four heroes (who have 11-14hp each and have one of their number capable of rezzing the others if they go down, but if they all go down then they're officially Incapped), and a guy whose power seems to be bad luck…as in, literally, he has really bad luck and it ends up in various people (usually himself or the bad guys) getting hurt :D.
Then there's the most recent expansion, Wrath of the Cosmos, which has some really difficult villains, one of which is pretty interesting in that the set-up is that you're in a giant arena thingy and you can earn Titles for doing certain things, and you don't win by defeating the villain but by earning Favour Points for basically beating up enough bad guys that the audience decides you're the best :D. I haven't had as much time to play Sentinels this last few months as I have previously so I haven't played this expansion so much. The heroes are pretty cool - one can change her size and has three character cards to show that (you switch between them as you change size). The other summons up energy construct things and plays them on his allies to give them a variety of bonuses and extra abilities and stuff :).
Upcoming in a few months or so is Villains of the Multiverse, which contains no new heroes but has a bunch of new villains who have the same grouping mechanic as the Vengeance ones (and can be mixed and matched with them). These ones aren't part of a team like the Vengeance Five, they're all separate in terms of story.
If you end up liking the game, you'll probably end up getting all of this stuff anyway :D.