I came to mention Brad Pitt after Meet Joe Black. But he’s taken so I’ll take Sandra Bullock in Crash.
Did you see Brokeback Mountain?
I never liked Richard Gere much until Primal Fear, then I forgot I liked him again until Chicago.
I thought Reese Witherspoon was the worst possible choice for June Carter, but she did far better than Joaquin’s Cash in I Walk The Line.
Never liked Christian Bale until The Prestige, now I can’t get enough of him.
Neil Patrick Harris. Forgettable kid actor, then…
What a comeback in Harold and Kumar Go To White Castle!
Martin Landau. My early exposure to him was in Space 1999. Ouch. But playing Bela Lugosi in Ed Wood, he rightly earned an Oscar.
You really should watch Victor Garber in Alias. Jack Bristow is one bad-ass mofo.
And then How I Met My Mother and Dr. Horrible’s Sing-Along Blog. I have not seen anything less than a fantastic performance from him whenever he’s on screen this past year.
I already mentioned Tom Cruise, dude. 
I immediately thought of John Travolta. I assumed he’d trading on cuteness until he just faded away when his Kotter days were forgotten. Than along came Pulp Fiction. Yeah, he’s done some crap since then, but still.
And the award for Sine Wave riding on a Roller Coaster surely goes to Eddy Murphy. Edgy 80s comedian (48 hours, Beverly Hills Cop), reduced to “will act to food” status (Haunted Mansion, Pluto Nash), Oscar nomination for Dreamgirls and then along comes Norbit.
Tom Cruise is an idiot cult dupe, but that doesn’t take away from his powerful acting in Magnolia, or how phenomenal he was in Tropic Thunder.
It’s a few years old now (1999, actually) but check out Bowfinger. You’ll find that Eddie Murphy and Steve Martin can both still be hilariously funny, and Murphy’s performance(s) will leave you wondering how in the fuck he ever makes a bad movie.
Interestingly, my first exposure to Landau was in 1966 in a Man From UNCLE episode, in which he played… a vampire. It was a campy over-the-top performance that left a good impression.
I think he made his bones in Hitchcock’s North by Northwest playing a very creepy personal assistant to James Mason. So, he’s always been capable, but some of his roles were pretty blah. He was mostly invisible in Mission Impossible, but all the actors there were cyphers.
Queen Latifa. She has become one hell of an actress.
Will Ferrell when I saw Stranger than fiction, although given the movies he continues to be involved in I’m leaning towards the view that that was a one off.
On a totally shallow note - Colin Farrell used to be entirely meh in terms of attractiveness whenever I saw him, then I watched Home at the end of the world and proceeded directly to ma bunk.
Wow, I’ve only known him as one of the greatest actors of his generation, so it’s interesting hearing about him before all that…
As for the OP, I’ll second Leonardo DiCaprio for What’s Eating Gilbert Grape? (I saw it after Titanic) and then Catch Me If You Can and The Aviator. He was a pretty boy who got by on being melodramatic and angsty, or so I thought, but then suddenly he started taking more nuanced roles and filling their shoes quite nicely.
Jim Carrey, though, wins this thread for me. I thought he was a talented physical comedian who seemed to be the poster child for stupid comedies. The Truman Show really took me by surprise here, and was the first role I really liked him in. He still had his physical on screen essence, but filled it out with more depth and feeling. Then he did Eternal Sunshine of the Spotless Mind and knocked it out of the park. He’s now in the upper echelon of dramatic actors for me (and in the lower echelon of comedic ones!).
In my defence (Apart from premature senility)I can only guess that we got the S&H T.V. series over here a bit later then when it was made in the U.S. but I have to say that in the light of what you’ve told me the 180 was from good to bad.
I have never seen Tom Cruise in a role where I think he gets lost in the role. I always see Tom Cruise “acting”, in fact I feel the same way about his interviews. I admit I have never seen Magnolia so I can’t comment on that one but in Tropic Thunder I saw Tom Cruise trying hard not to be Tom Cruise but still obviously being Tom Cruise.
He’s one of a handful of actors that I just assume I’ll hate, but lately I like everything he does.
Nick Nolte is another. I’ve been on this “hate him…wait a minute, I love him” thing for about 20 years!
I’ll go the other way. I used to absolutely adore Bill Murray all the way up to The Royal Tenenbaums. He always seemed to be willing to push things as far as he could get away with and he was funny. He did Lost in Translation and apparently became enamored of the disconnected way he played that role - no connection to other cast members, the audience or the story; and continued that for all his future roles. He now induces a yawn the moment he appears in a scene.
For all the people who “discovered” Di Caprio at Titanic or later, he had a fantastic filmography before that, did any of you see This Boy’s Life, What’s Eating Gilbert Grape, The Basketball Diaries, Total Eclipse, Romeo + Juliet or Marvin’s Room, all of which were made before Titanic and DiCaprio is great in each of them. I thought when *Titanic * came out that he was the star name meant to carry it.