From a geographical perspective, the only way for Janeway to cross through Borg space was to ally with either the Borg or 8472.
The very first thing that 8472 did when they encountered the Voyager crew was attack Harry Kim, punching him so hard that he nearly died from the cells left in the wound. The next thing that 8472 did was fire on their ship with enough force to get a ship with the mass and durability of Voyager to spin like a top. Janeway probably looked at this and thought "Jesus! These people are more hostile than the Borg!".
At the same time, the only way Voyager's crew could even start an alliance was to bring something to the table. They had something for the Borg, in the form of the nanoprobes. But they had nothing for 8472. The Borg were the only option.
To answer your question of why they didn't use every technology at their disposal for a first contact, they tried to contact 8472. Kes used her telepathy to contact them. 8472 promptly shot at them. This kind of sets a bad precedent.
Yes, neither of them liked the Borg at all. But 8472 was more of "We hate you all!" rather than "We hate the Borg!". Not only does this fly directly against Janeway's principals, which would result in an unstable alliance at best, but it's difficult to ally with people who despise you.
There was also an element of long term planning. When 8472 was done with the Borg, which was within less than a few months time, 8472 was going to target other species as well, "your galaxy will be purged". If these people can take out the Borg in less than a decade, the rest of the galaxy is screwed. This was the smart move in the long run.
In summary, Janeway allied with the Borg, because in her mind, it was literally the only option.