Reeves was already established when he made Speed. He had previously starred in Point Break, My Own Private Idaho, Bram Stoker’s "Dracula, and Little Buddha. His first breakout role was as Ted “Theodore” Logan in Bill and Ted’s Excellent Adventure and its sequel, Bill and Ted’s Bogus Journey.
I’m going to also mention Kevin Bacon in Footloose and Matthew Broderick in War Games.
Andy Griffith, A Face In The Crowd.
Jessica Lange, 1976 version of King Kong
The OP specified lead or movie-stealing supporting roles, not necessarily bit parts. I’d say Risky Business qualifies for Cruise.
Winning an Oscar in her first starring (rather than supporting) role is what I’d call a real career-launcher! 
I submit Julie Andrews in Mary Poppins.
Prior to that her screen credits were a couple of tv movies.
Tim Curry in Rocky Horror Picture Show.
When he entered the scene in his bustier and stockings, I thought, “That man’s a star.”
Also submitted by Roderick Femm in post #4.
Alan Rickman in Die Hard.
I’m surprised it took so long to mention him.
But this seems to be missing the point of the thread. Obviously every major star had some role that put them at the top. But this thread is about the people whose first role did it.
Marlee Matlin won an Oscar for her first role (in Children of a Lesser God).
Mel Gibson in Mad Max
Martin Sheen and Sissy Spacek in Badlands (although Sheen apparently had done tons of TV work by that time)
I was going to say Jack Nicholson in Easy Rider but he had several significant roles in B-movies before that
Jeff Bridges and Cybill Shepherd in The Last Picture Show
The Hollywood debut of Mae West in Night After Night - this one scene alone propelled her into superstardom. She was actually a bit player with a third-string subplot, but nowadays nobody remembers anything else from the movie other than it was her screen debut.
True, but he was already famous due to SNL wasn’t he?
That’s sort of like mentioning Michael J. Fox and Back to the Future(I think it was his first movie).
As did Anna Paquin (for The Piano).
But the OP asks about becoming a star in their first role, not the first role that made them a star.
Peter O’Toole in Lawrence of Arabia. He’d had a few bit parts previously, but that was his first leading role.
I don’t think this qualifies, but I just wanted to mention that last night while watching Christmas Vacation, after having seen it probably hundreds of times, was the first time I’d realized that Johnny Galecki is Rusty Griswold.
Yes. Not a common debut, but an exceptional debut.