The empire isn't an opressing entity and skyrim has been core part of the empire since it's foundation.
"Freedom" from Ulfric would mean mass discrimination against anyone who wasn't a nord and lived in skyrim, not to mention that Ulfric is hardly a bearer of freedom. Ulfric proposes "old ways" which mostly are "might makes right" and abolishement of the englightened attitude of the empire.
Nords might have good warriors, though it's impossible to evaluate how they would be capable of fighting in formations and large battles and not small skirmishes. Nords also happen to have very few proficent spellcasters and the more "rogue-ish" kind of fellows which would leave them very handicapped against the dominion.
I remember in morrowind even one of those nationalistic dunmers said that the "Imperials are weak when alone, but unbeatable when marching side by side" for example. Capabilities in 1v1 =/= capabilities in large battles, think maaaybe Romans vs Gauls loosely.
A skyrim where Talos was openly worshipped might as well just be the provocation the dominion needs to invade, it has nothing to do about skyrim being the only ones suffering from worship of Talos being banned. The dominion is what imposes the limitations on Talos worship and not empire out of free will, the Altmer are upset that they believe a human is unworthy to become a deity and as such would use the same excuse to invade skyrim.
An alliance, even if formed, would be very uneasy and distrusting of one another. The fracturing would destroy any chance of opposition the dominion. Not to mention skyrim wasn't a vassal of the empire, but an intergral part since the very first days of it.