Since Skyrim was my first game, I was also inclined to believe the Empire was all-around evil and authoritarian when they tried to cut my head off. I held off on the Civil War just in case and because it wasn't one of my priorities. Eventually, I very reluctantly joined the Imperials.
Anyways, when you say you want a "justification" for your Orc to join the Stormcloaks, you don't really need any more of a justification than you would if you were joining the Imperials. TES is chock-full of grey areas and ambiguity. Since you are worried about how an Orc would be perceived by Stormcloaks due to the attitudes of many of them, consider a couple things.
1) Not every Stormcloak is a racist. A large majority of them are just concerned with independence and preservation of their culture.
2) EVERY province and race has its fair share of racists. It doesn't matter where you go. In fact, if you ever play Morrowind you will find that the Dunmer of Vvardenfell are arguably more xenophobic than the racist Stormcloaks you encounter.
Some of the previous posters have already given you a few reasons for you to "justify" an Orc Stormcloak. You have to decide how to fit it with your character, but those responses that others gave are a start. I'll throw one in that I don't think I have seen yet: being an Orc, you feel that the Empire has done a piss-poor job in granting Orsinium that provincial status that it has so desperately longed for (as in, not giving it provincial status at all). Orsinium's latest sacking occurred in the early 4th Era, once again at the hands of combined forces from Hammerfell and High Rock. Uriel Septim VII was reviewing their application for provincial status, but it is kind of hard to grant it when you get assassinated. The Medes apparently didn't really have much interest in granting said status to Orsinium. So, maybe your Orc wants to stick it to the Empire, and joining the Stormcloaks to kick the Imperial forces out of Skyrim would be the ultimate middle-finger you could provide.