Howard Stern - fired from one of his first radio gigs
Bill Watterson - fired from his first job his first newspaper job - and went on to create Calvin and Hobbes
Ozzy Osourne - fired from Black Sabbath
Steve Jobs - I guess this might be stretching the definition of early, but one of the most famous (or infamous) firings I can think of.
Didn’t slow them down one bit it seems. Any others you can think of?
Colonel Sanders seems to have been fired repeatedly in his early career. Mainly for brawling. He gave up law after beating up his own client in the middle of the court room! Maybe one of the secret spices is derived from the blood of his enemies.
Brad Pitt was supposedly fired from a job as a movie extra, early in his career. No cite, sorry, it may just be an urban legend among disgruntled extras.
Ray Romano was cast as the station technician on NewsRadio - the role that eventually went to Joe Rogan - and was fired just days before they shot the pilot.
Glenn Ford was originally cast as Clay Morrow in Sons of Anarchy, and a substantial part of the pilot shot before he was replaced by Hellboy. I’ve never heard a good reason except that Perlman was the first choice and became available.
Madonna said she was fired from Dunkin’ Donuts, although the reason she gave for being canned - squirting jelly on the customers - sounds kind of dubious to me.