Akash'bhuta depends on the environment. Put her in an environment lacking targets and she's easy. Put her in the Tomb of Anubis and prepare for a fight.
Or Advanced mode with a target-sparce environment makes for some very good "easy" games as well
The Grasshopper and I got shellacked together in the Tomb (his choice, not mine); the newbie game where we got steamrolled was in Insula, IIRC.
Tomb of Anubis is probably not actually harder than Rook City. However, I have won 4 of my 9 games in Rook City, and only 3 out of 11 games in the Tomb, so I'm definitely more scared of the Tomb at this point (not that there isn't some fear of RC keeping me from increasing my count of games there).
The scaling on the damage on different cards means the number of players has a huge effect on how hard a given environment or villain is. Most of the games I've played have been two-player with my just my girlfriend and myself.
Akash'Bhuta is relatively easy in two-player mode, as long as both characters can deal some damage. Most of the damaging cards either deal H-2 or H-1 damage, meaning her damage output in a two-player game is negligible. In the games we lost, it was because we had one support character and one damage dealer, and the damage dealer dropped to lower life and got taken out by Ensnaring Limbs.
We've only tried Dawn once, but she was pretty easy. You don't have to wait very long for her to flip back when you're only waiting for two Citizens to show up, meaning her indestructibility isn't too onerous.
In contrast, Voss seems almost unbeatable with only two players. The minion damage doesn't scale at all, so you end up taking obscene amounts of damage from them very quickly. You also just can't produce enough firepower to burn down the space ships when they show up, much less do it while keeping the minions in check. That's not to say he's trivial in a 5-player game, but I think he's much easier. Since the most prevalent scaling effect is on the starting number of minions, once you burn those down, extra players are almost entirely upside.
I have much fear of Rook City. Not as much for the Tomb, although when the Tomb feels like being harder than the villain, it certainly has that capability
When I play in the Tomb, whether it's a cakewalk or a nightmare tends to revolve around Urshe. Sometimes he gets rid of a lot of nasty stuff and only plays Shamise, and sometimes he discards the Idol of Anput and plays Trial of Fire, Swinging Blades and Swarm of Scarabs.
Overall I tend to find it somewhat less difficult than Atlantis and much less difficult than Rook City, but it's definitely up there.
When you say your playing with two players, do you mean two heroes? Just want to make sure you know it's not meant to be played that way - it's not balanced. (Two players should be played with two heroes each or something like that.) H should never be less than 3.
If you already know, it's all good - I just want to make sure! 
Of course, you're welcome to home-rule anything you want, but I want to make sure you know that's what your doing. You don't want to compare home ruled games with games that are balanced with play testing and such. 
See, and I've only lost a single game in Atlantis I think, although at least one other was extremely close (and against Ambuscade of all people, not even on Advanced; there was just one hit point left out of four heroes by the time he went down). I know that the potential exists for Font or Pillars to play something horrible during the villain Start phase which instantly activates, but I haven't seen it so far. And with that risk aside, the Environment is more of a nuisance than a threat; the Kraken usually helps us by picking off minions, and Phosphorescent Chamber is frequently quite helpful. Toxic Seaweed is pretty bad, but seldom hard to get rid of, and Hallway Collapse is no big deal as a rule. That leaves Mystical Defenses, which attack both teams equally, and Leaky Room, which is annoying but temporary, and at least once we've gotten a lot of mileage out of the extra lightning damage. As for the Font and Pillars, while they definitely pose a threat, they also offer the heroes some significant benefits, and in almost all my games where this has come up, the swing has been hugely in our favor.
I must remember to try the Matriarch in Atlantis sometimes, and leave the Pillars out forever, just for the sheer hilarity of reshuffling and flipping her probably several times each round. (Also, I've never had the Pillars AND the Tomb at the same time, so just for laughs I'll have to do that. I'd want to pick a pretty safe villain if I was going to leave the Pillars up for a second Environment turn, but it'll be totally worth it.)
Phosphorescent Chamber is extremely nasty when combined with any Villain that forces discards, like The Dreamer, Ermine, Osiris, Citizen Dawn, or Iron Legacy, especially if you don't manage to draw any Environment destruction.
The discard is quite painful to be sure, but often the damage boost and/or the healing boost is worth it. I've probably not fought too many of those matches though.
For me it's usually the Krakens that cause problems. Against villains like Plague Rat or Iron Legacy, it can be really easy to get trapped as the lowest HP target. They're pretty good at killing Citizens you wanted to keep, too. All the Atlantis targets also have oodles of HP, so if you don't have environment destruction handy that's 30+ damage that could have gone to the villain. For me at least the Krakens have a tendency to come out at especially inopportune times, like when we'd left one Kraken alive to chew on a villain target and a second Kraken comes out to chew on a hero. Extra villain plays from Font/Pillar are always annoying, but fortunately I've only ever had Pillars bring out an EPE at the start of the villain turn once.
The Pillars are so bad because the villain gets so many extra card plays relative to the heroes, the longer you leave it out :P.
Krakens are annoying because they bash someone immediately after being played (well, after any other end-of-turn stuff in the same turn, I mean). At least with the Monorail you have a round in which to try and make it go away if it's gonna hit one of you ;).
We used the Pillars and the Informant to reshuffle the Chairman's deck on G+ one time. It made the rest of the game pretty easy because there were no thugs to pull the rest of the game. That the pillars allowed us to play extra cards just meant we were super set up for the next round when we got to pound on the underbosses
I had a game against Kismet in the ruins of Atlantis that ended up being pretty funny because the targets came out in the order kraken- mystic defences-kraken and as the talisman was the lowest target it meant that the environment was continually throwing it back and forth between kismet and the heroes, and it ended up that she was always on her side when she doesn't have the talisman because she'd not have it at the start of her turn, but the two damage she deals to it would take it back to her, but then the environment would give it back to the heroes on its turn and the cycle would repeat.
on the other hand I lost my first solo game there against normal baron blade of all people- mostly because I didn't realise the environment could attack villain targets, but those extra plays for blade seemed to bring out nothing but hastens :(
in terms of favourite villain, I've not played much but so far I like the dreamer (for both the story and the actual gameplay, as well as luck being a huge factor in whether you win or not) and Ambuscade for being a relatively quick and usually easy match for when I'm a bit tired. I also enjoy blade (both versions) as he's not go too much to keep track of when playing.
The damage boost and the healing boost affects Villain and Environment cards too, though. In general I find that global damage boosts are more dangerous to the Hero team than beneficial, and other global damage boosts don't cripple your hand.
We tend to try and get rid of the Phosphorescent Chambers rather than let them stay out for ages - while extra damage and healing is nice (as long as you're benefitting from it more than the villains, that is), it's the forced discard that we don't like. So if we can't get rid of it by nuking it with something then we just do the Start phase discard when the environment's turn comes round again.
5 - Kismet When I first played Kismet, I thought she was perfect. Despite my historical dislike of luck-based powers, her flavor was really strong, I was legitimately surprised by both the mechanical and personality change when she flipped (and they reinforce each other nicely), and the game was brutally difficult for my team. I lost narrowly, and was in love. Over time, this has faded slightly - good Ongoing destruction sadly neuters the violent trickster, reducing her to a mere gimmick - but as gimmicks go, she may be SotM's best, so she still has a place on my list.
4 - Proletariat I am always surprised by Proletariat's popularity. Not because he isn't a deeply compelling and cool character, which he absolutely is, but because he lacks the things I would expect to really make that stick with people. In my experience, he's the Vengeful Five villain most likely to die without doing anything notable (and then reveal a flip side which only Tachyon cares about), and the one lacking a clear tie to his nemesis. Yes people love him in spite of that, or maybe because of it - whether he smashes face or falls apart, his role in any game is memorable, and if he's not tied to Absolute Zero, it's because he is tied to interesting themes and ideas of his own - something the likes of Friction or Fright Train could stand to learn from.
3 - La Capitan So much fun. She's got personality, she (on Advanced) keeps constant pressure on your setup without making it just impossible to even try, even her minions are as much fun as some villains - and they just keep coming back for more! Sure, nobody really knows what ties her to the rest of the game, or what exactly her flip side even means, but that's not the point. The point, mateys, is that pirates rule!
2 - Citizen Dawn As a long-time Magneto fan, it took a little while for me to adapt to Dawn's much more Jonestown spin on that theme. But that's really the genius of Dawn, both in flavor and mechanics - she has just enough familiar elements to work, but always takes adjustment, whether that's changing your plans to deal with the different sets of Citizens (then scrapping your plans entirely when the Aurora eats everything you've worked for) or coming to terms with the unique threats posed by a truly mad dictator.
1 - Omnitron There may not be much the evil robot does best. Whether it's damage or defense extra plays or stuff destruction or flavor, someone always goes further. But Omnitron is no slouch in any department, and while the result isn't exactly exciting, it may well be the most consistently strong and interesting game in SotM. Give the bot some love.
@ Ironic: Omnitron as one of the most consistent threats? I really can't agree with you on that one. Visionary just utterly destroys him almost single-handedly. Being Suggested to play harmless cards over and over again makes him just sit there, Wrest the Mind neutralizes his Bomb, and she has no equipment for TechSing. Even without her, however, I seldom find him a hard fight. He's a little more likely to pull out a surprise win than Blade, but his Difficulty 1 status is well-deserved. With the exception of Flechettes and maybe TechSing, he just never does enough damage to pose much of a threat without giving you the opportunity to defend yourself before the blow lands; just keep blasting either his EPEs or his Component-laden self, and he'll never pose more than a very mild threat. If I wanted him to be mean, I'd make his Skittery Stabby Things damage all hero targets instead of just the highest, at least double the HP he regains from Repair Bots, and make all the bots significantly tougher, along with maybe having him start with something in the trash so he doesn't usually miss his first "rebuild a Drone or Component" action. Heck, maybe make him rebuild several Drones at once; he's supposed to be a factory, let him mass-produce. As it is, with the exception of a couple of really mean cards, he mostly just doesn't do enough to pose a serious threat.
Heheh, yes, playing Calvinball with the Talisman is fun. My last game against Kizzy, I'd played on Advanced before, but I think it was the first time I noticed that her +1-3 damage on the flipside applies to the damage she deals the Talisman in order to get it away from the heroes. So in a 3-player game, she blasts it for 3 each turn and a hero can maybe keep it for 3 turns after the first, but in a 5-some, she's dealing 5 damage to it, then dealing a hero 10 damage (Talisman starts at 7 HP in a hero's play area, Kismet deals 2+3 irreducible to it, leaving it at 2 HP, then she deals 9-2+3 damage). So nobody can ever hold it for more than 2 total turns, and the highest-HP hero had better be Nightmist with her Amulet or visionary in a Cocoon, otherwise the team's collective HP will drop like a rock.
in terms of favourite villain, I've not played much but so far I like the dreamer (for both the story and the actual gameplay, as well as luck being a huge factor in whether you win or not)
Wait, that last part is a positive to you? I like that luck provides great variety in the game, but Dreamer is pushing toward the point where you can play really well and still lose just due to bad luck, and I don't care for that fact. I like for a villain to pose a very consistent threat which isn't too vulnerable to countermeasures (this is why I consider the Matriarch to be the weakest of the diff-4 villains; just one point of DR makes such a huge difference to how much harm she can inflict, and Savage Mana or Take Down or a few other cards can just utterly make her cry), but also isn't too likely to dial up into the realm of the utterly psychotic as a result of pure chance (if it's the result of you playing poorly, of course, that's different). Dreamy has a lot of really spoilery cards like Dark Hero and the mass-damage one-shot; it sucks when she gets too many of those too soon, and I feel as though there was never even a possibility I might have won, which is not a happy feeling. (At least with the Chairman, I go in expecting to lose; strangely I've actually beaten him more often than Dreamer, though possibly some of those victories were somewhat dishonest).
Eheh, you may have me there, Edwin - I almost never use Visionary, and have houseruled Infrared Eyepiece to be a One-Shot, since most villains fold like cheap lawn furniture when the Heroes can determine their plays. Really, the only exceptions I can think of offhand are the Vengeful Five (because they have multiple decks to draw from), and The Chairman (who's vulnerable to Brain Burn instead).
Visionary is easily among my favorite heroes, but I only get her out for the absolute toughest games, as a rule. Not unlike Legacy (though slightly cooler).