I've played the game solo three times now, once with one investigator, and (discovering that that virtually forces you to play for the final battle, and preferring a gate-sealing victory), twice with two investigators. I won every time, and in fact, it was never really even close. And people seem to think that the game gets easier with more investigators, so I can't imagine much chance of losing with more.
I am playing the base game only, no expansions, and I've read through the rulebook several times, as well as playing in a five-player game with someone who knew the game well, so I don't think I'm doing anything major wrong. I did discover post-game-two that I'd once made the mistake of forgetting to exhaust a Withering spell when used, thus applying it several times in a turn against successive monster fights in a single location, but I don't think this made a big difference to the outcome, and I only did it once.
In particular, the following seem to be the case:
1) Unless you adopt a generally dubious strategy of closing but not sealing gates, it's very hard for the AO to awaken due to the doom track (only Yig, due to his 10-doom and doom-increasing-ability, is remotely likely to). If the AO does awaken, it will almost always be due to the terror level rising to 10 and too many monsters arriving. Since there are only 11 unstable locations (and four of them open gates very rarely), more than 11 doom tokens is impossible under normal circumstances. And if you use even one elder sign, no AO but Yig can possibly hit the maximum doom track level.
2) Nyarlathotep and Shub-Niggurath are almost ridiculously easy to beat with few players if you simply prepare for the final battle. Grabbing all possible clue-tokens/ monster-trophies is really not hard. Ithaqa, Yig and Hastur (in that order of increasing difficulty) are similarly quite easy to beat in the final battle if you grab good enough equipment. Only Cthulhu and Yog-Sothoth make for a really hard final fight (Cthulhu because of his regeneration and high combat-modifier; Yog-Sothoth because gate trophies are hard to acquire and require you to go for a gate-closing strategy anyway); Azathoth being impossible, obviously. It seems like the game is encouraging you to ignore gates most of the time and build up combat capbilities. Because the AO can't awaken from doom tokens, and the terror track can be kept in check by beating up on monsters (which coincidently, also requires good combat capabilities), this generally lets you have all the time you need to "level-up", as it were.
3) The real threat in the game is not the AO, but the rumour cards. A really horrible rumour (The Terrible Experiment or Good Work Undone if you're going gate-sealing), can seriously affect the game difficulty. Conversely getting a weak rumour (Southside Strangler, arguably Digging up the Dead) into play and leaving it there to stop any nastier ones appearing is very good.
4) Gate-closing victories seem almost impossible, unless you're playing 1-investigator and the Mythos deck hits the same location four times in a row or something. Generally, if you're getting close to closing all gates, you've also sealed enough for a gate-sealing victory.
I've now beat Cthulhu and Yog-Sothoth 2-investigators (both times by sealing gates), and Shub-Niggurath 1-investigator by final battle. It doesn't look like any of the remaining AOs offer any significant challenge, unless I try Azathoth with 1-investigator: that sounds quite tough.