I beat the crap out of Miss Information with Parse, Haka, and Fanatic* in Pike Industrial. Miss Information was actually defeated by an exploding irradiated cyclohexine vat, which made me quite happy.
I didn't take random heroes against Miss Information the first time, either - I took Legacy, Absolute Zero, Wraith, Tachyon, and Bunker. Miss Information had enough ongoing + equipment destruction going (because of five heroes, and because multiple cards added to it) that I couldn't accumulate any equipment with any of the characters. I think the real problem that took the heroes down, however, was picking Freedom Tower as the environment and getting pretty much all the forced entry points in play. I did not realize that the Freedom Five was so unsuited to fighting Miss Information, and I also did not realize that Freedom Tower was such a potentially harsh environment and I made some bad calls about not removing certain environment cards.
I didn't have any issues with ongoing destruction, as I was able to remove all of her clues as soon as she flipped and kept them gone.
When I said regarding the other thing "It was pretty brutal" I meant it was brutal to Voss, who was frozen to glass-like brittleness by Absolute Zero opening all of his apertures and dealing 30+ cold damage in one turn and leaving Voss at -12 or so.
Anyway, all that said, I love to click random on the app, and I use Spiff's randomizer at least half the time I play anything, and while I have lost a few of those fights I find I can go back to them with a better chance of winning due to knowing how the villain, heroes, and environment worked. I have yet to lose a random game on the app, although there's a lot less variety to choose from so far.
Not to dismiss your advice, I am just not entirely clear why you mentioned random heroes when the game I described with random heroes was a clear win, and the game I described losing was not due to random selection.
* fixed - I had prime wardens on the brain