Besides, nords are pro religion and worship. Ulfric would look like a complete hypocrite by allowing talos worship and then banishing the worship of yet another god-like being.

Malacath was Trimimac, the god who cut out Shor's heart. So it's not inconceivable that Nords would want to outlaw his worship.

Nords frequently love to shout "Skyrim is for the Nords!" By that I take it to mean that it's not for anyone else, Orcs included. And they certainly detest the Dunmer; look at their living conditions in Windhelm. And while it's true that no one likes the Thalmor, they're yet another non-Nord race the Stormcloaks despise. And of course they don't like Imperials either.

An Orc should join the Legion. It doesn't really matter at all but if one is trying to role-play the thing then it would be silly for an Orc to join the Stormcloaks. If it was a football game it'd be like tackling the guys on your own team.

Nords helped to destroy Orsinium. There's a long history of trying to deny the orcs the right to a state. End of story, really.

And anyone who doesn't understand the meaning of the slogan "[blank] for the [blankians]!" BADLY needs to take a history course of some sort.

I guess she would join the empire then, but she won't be very excited about it. She would probably be the character that wants to convince the empire to fight against the thalmor.

The Empire has always been fair to Orcs. In fact, The Empire is the only one that has actually helped
the Orcs and recognized their claim to Orsinium. The Orcs have absolutely no reason to hate the Empire
or to help the Stormcloaks.

And if we're sticking with the lore, rebellious Shamans wouldn't last long in Orc strongholds.

EDIT:
In fact, there aren't any other race that would have less reason to support Ulfric Stormcloak.
Let's review:
Argonians: Black Marsh is now independent, and a united Empire would threaten their independence.
Khajiit: Same thing as with the Argonians, apart from the fact, that Elsweyr is officially in cahoots with the
Aldmeri Dominion and the Thalmor. A weakened Empire would benefit them.
Redguards: Angry with the Empire selling them out to the Dominion with the White-Gold Concordat, they
can relate to the wish for independence.
Imperials: Alot of Imperials were born outside of Cyrodiil, and have been known to adapt to other cultures
more rapidly and thoroughly than other races. It wouldn't be that strange for an Imperial to support Ulfric.
Altmeri: Same as with the Khajiit. A weakened Empire = Better chances for taking them down.
Bosmeri: Same as with the Altmer.
Dunmeri: While the Dunmer have little reason to support Ulfric, they are more likely to, seeing as how the Empire
couldn't do anything to prevent the Argonian invasion of Morrowind.
Bretons: Same as with the Imperials - Bretons didn't play a very big part in the Great War, and has been very
incognito during the struggle for power in Tamriel. A Breton could have loads of reasons for supporting the Stormcloaks.
Nord: For obvious reasons, they form the bulk of the Stormcloaks forces.

As for the Orcs, as I've mentioned, the Empire has always supported the Orcs in their struggle for independence and recognition.
In return, the Legion has benefitted greatly from Orc blacksmiths and their ferocious warriors. A mutual and prosperous deal.

Nords helped to destroy Orsinium. There's a long history of trying to deny the orcs the right to a state. End of story, really.

I guess she would join the empire then, but she won't be very excited about it. She would probably be the character that wants to convince the empire to fight against the thalmor.

EDIT: But if she joins the empire she would fear the banishing of more gods, like R3NEGADE mentioned.

Uggghhh....this is just so hard.

I'd say that the local Nords do not like the Orcs.

When i walk into a city and a guard says "That stronghold, its very existence is an affront to my people" pretty much gives the first hint that the stormcloaks would not be welcoming.
The Empire on the other hand has long prized Orcish smiths for their craftsmanship and also used Orcs in heavy armour as shock troops.

Makes more sense I think.

Still the main people who would support the Stormcloaks in my view are the human races for the simple reason of Talos worship being much closer to their hearts, Hammerfell never accepted the terms of the concordat and was cut loose from the empire and handed to the Thalmor because of their refusal to ratify it, likewise Nords and Imperials both can be very uneasy about it as well, possibly Bretons also and that might give them a reason to side with them under the Talos rallying cry.

First time, yes. Second time, no. The refugees from the attack fled TO skyrim. That'd be a little awkward. They seemed buddy buddy while attacking morrowind during Oblivion's time.